2015
09-17

# Find Permutation

Given b0, b1, …, bn-1, find two permutations {ai}, {ci} of 0..n-1 such that ai+bi=ci (mod n) for every i.

First line, number of test cases, T.
Following are 2*T. For every two lines, the first line is n and the second line contains n integers.

Sum of all n <= 105.
0<=bi<n
It’s guaranteed that there exists a solution.
Test data is generated by randomly choosing two permutations and subtracting one from the other.

First line, number of test cases, T.
Following are 2*T. For every two lines, the first line is n and the second line contains n integers.

Sum of all n <= 105.
0<=bi<n
It’s guaranteed that there exists a solution.
Test data is generated by randomly choosing two permutations and subtracting one from the other.

1
3
0 1 2

2 0 1
2 1 0

### 代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1e5 + 5;

int N, A[maxn], B[maxn], C[maxn], P[maxn];

int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%d", &N);
for (int i = 0; i < N; i++) scanf("%d", &B[i]);
for (int i = 0; i < N; i++) A[i] = C[i] = P[i] = i;

for (int i = 0; i < N; i++) {
int u = i;
while ((A[u] + B[u]) % N != C[u]) {
int v = P[(C[u] - B[u] + N) % N];
swap(A[u], A[v]);
swap(P[A[u]], P[A[v]]);

if (v > i) break;
swap(C[i+1], C[v]);
u = v;
}
}
for (int i = 0; i < N; i++) printf("%d%c", A[i], i == N-1 ? '\n' : ' ');
for (int i = 0; i < N; i++) printf("%d%c", C[i], i == N-1 ? '\n' : ' ');
}
return 0;
}