1650D - Twist the Permutation - CodeForces Solution


brute force constructive algorithms implementation math *1300

Please click on ads to support us..

Python Code:

from collections import deque

def solve():
    n = int(input())
    ans = [0] * (n + 1)
    deq = deque([int(i) for i in input().split()])
    for i in range(n, 0, -1):
        while deq[len(deq) - 1] != i:
            deq.append(deq.popleft())
            ans[i] += 1
        deq.pop()
    for i in range(1, len(ans)):
        print(ans[i], end = ' ')
    print()
            

for i in range(int(input())):
    solve()

C++ Code:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define forn(i, n) for (int i = 0; i < int(n); i++)


void solve() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int ans[n];
    for (int i = n; i > 0; --i) {
        int ind = 0;
        for (int j = 0; j < i; ++j) {
            ind = a[j] == i ? j : ind;
        }
        int b[i];
        for (int j = 0; j < i; ++j) {
            b[(i - 1 - ind + j) % i] = a[j];
        }
        for (int j = 0; j < i; ++j) {
            a[j] = b[j];
        }
        ans[i - 1] = i != 1 ? (ind + 1) % i : 0;
    }
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}
int main() {
    int tests;
    cin >> tests;
    forn(tt, tests) {
        solve();
    }
}


Comments

Submit
0 Comments
More Questions

454A - Little Pony and Crystal Mine
2A - Winner
1622B - Berland Music
1139B - Chocolates
1371A - Magical Sticks
1253A - Single Push
706B - Interesting drink
1265A - Beautiful String
214A - System of Equations
287A - IQ Test
1108A - Two distinct points
1064A - Make a triangle
1245C - Constanze's Machine
1005A - Tanya and Stairways
1663F - In Every Generation
1108B - Divisors of Two Integers
1175A - From Hero to Zero
1141A - Game 23
1401B - Ternary Sequence
598A - Tricky Sum
519A - A and B and Chess
725B - Food on the Plane
154B - Colliders
127B - Canvas Frames
107B - Basketball Team
245A - System Administrator
698A - Vacations
1216B - Shooting
368B - Sereja and Suffixes
1665C - Tree Infection