1746C - Permutation Operations - CodeForces Solution


constructive algorithms greedy implementation math

Please click on ads to support us..

Python Code:

from sys import stdin, stdout
import math

from itertools import permutations
import random


mod = 1000000007
mod9 = 998244353
fact = []


def power(x, y, p):
    res = 1
    x = x % p
    while y > 0:
        if y & 1:
            res = (res * x) % p
        y = y >> 1          x = (x * x) % p

    return res


def largePower(a, b, MOD):
    b = str(b)
    remainderB = 0
    for i in range(len(b)):
        remainderB = ((remainderB * 10 + ord(b[i]) - 48) % (MOD - 1))

    return power(a, remainderB, MOD)


def decimalToBinary(n):
    return bin(n).replace("0b", "")


def binaryToDecimal(n):
    return int(n, 2)


def buildBitmask(n, ans, arr):
            if n == 0:
        arr.append(ans)
        return
    buildBitmask(n - 1, ans + "0", arr)
    buildBitmask(n - 1, ans + "1", arr)

    return


def buildFact(n, m):
        fact.append(1)
    for i in range(1, n + 1):
        fact.append(fact[-1] * i)
        fact[-1] %= m

    return fact


def buildSieve(n):
    prime = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1

    return prime


def findDivisors(n):
    i = 1
    arr = []
    while i * i < n:
        if n % i == 0:
            arr.append(i)
        i += 1
    m = int(math.sqrt(n))
    for i in range(m, 0, -1):
        if n % i == 0:
            arr.append(n // i)

    return arr


def binSearch(l, r, arr, x):
    ans = -1
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] > x:
            r = mid - 1
        else:
            ans = mid
            l = mid + 1
    return ans


def solve(test):
    #    n = int(stdin.readline())
            a = list(map(int, stdin.readline().split()))
    d = []
    for i in range(1, n):
        d.append([a[i] - a[i-1], i])
    d.sort()
    ans = [1]*n
    cur = 2
    for i in range(n-2, -1, -1):
        if d[i][0] < 0:
            ans[cur - 1] = d[i][1] + 1
                    cur += 1
    for i in ans:
        print(i, end=' ')
    print()
    return


if __name__ == '__main__':

    tests = int(stdin.readline())

        for _ in range(tests):
        solve(_ + 1)

C++ Code:

#include<bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
typedef tree<pair<int,int>,null_type,greater<pair<int,int>>,rb_tree_tag,
	tree_order_statistics_node_update> indexed_set;
 
#define ll long long
#define ld long double
#define FOR(i,k,n) for(int i=k;i<(int)n;i++)
#define AND &&
#define OR ||
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define ENDL "\n"
#define PI 3.141592653589793238462643383279502884L
#define MOD (ll)(1e9+7)
#define LLMIN(a,b) (((a)<(b))?(a):(b))
#define LLMAX(a,b) (((a)>(b))?(a):(b))
#define N (int)(2e5+1)
#define MIN(x,y) (((x)<(y))?(x):(y))
#define MAX(x,y) (((x)>(y))?(x):(y))
#define INV 499122177LL
#define EPS 1e-7
#define dequeue(x) x.front();x.pop()
#define INF (ll)1e18
 
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pli;
typedef pair<ld,ld> dd;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int t=1;
	cin>>t;
	
	while(t--){
		int n;
		cin>>n;

		int arr[n];
		for(int i=0;i<n;i++){
			cin>>arr[i];
		}

		int ans[n];
		for(int i=0;i<n;i++){
			ans[n-arr[i]]=i+1;
		}

		for(int i=0;i<n;i++){
			cout<<ans[i]<<" ";
		}
		cout<<ENDL;
	}

	return 0;
}


Comments

Submit
0 Comments
More Questions

1650C - Weight of the System of Nested Segments
1097A - Gennady and a Card Game
248A - Cupboards
1641A - Great Sequence
1537A - Arithmetic Array
1370A - Maximum GCD
149A - Business trip
34A - Reconnaissance 2
59A - Word
462B - Appleman and Card Game
1560C - Infinity Table
1605C - Dominant Character
1399A - Remove Smallest
208A - Dubstep
1581A - CQXYM Count Permutations
337A - Puzzles
495A - Digital Counter
796A - Buying A House
67A - Partial Teacher
116A - Tram
1472B - Fair Division
1281C - Cut and Paste
141A - Amusing Joke
112A - Petya and Strings
677A - Vanya and Fence
1621A - Stable Arrangement of Rooks
472A - Design Tutorial Learn from Math
1368A - C+=
450A - Jzzhu and Children
546A - Soldier and Bananas