思路逆着想，观察下状态，和一些规律，有时会有奇效。
D. Twist the Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Petya got an array aa of numbers from 11 to nn, where a[i]=ia[i]=i.
He performed nn operations sequentially. In the end, he received a new state of the aa array.
At the ii-th operation, Petya chose the first ii elements of the array and cyclically shifted them to the right an arbitrary number of times (elements with indexes i+1i+1 and more remain in their places). One cyclic shift to the right is such a transformation that the array a=[a1,a2,…,an]a=[a1,a2,…,an] becomes equal to the array a=[ai,a1,a2,…,ai?2,ai?1,ai+1,ai+2,…,an]a=[ai,a1,a2,…,ai?2,ai?1,ai+1,ai+2,…,an].
For example, if a=[5,4,2,1,3]a=[5,4,2,1,3] and i=3i=3 (that is, this is the third operation), then as a result of this operation, he could get any of these three arrays:
- a=[5,4,2,1,3]a=[5,4,2,1,3] (makes 00 cyclic shifts, or any number that is divisible by 33);
- a=[2,5,4,1,3]a=[2,5,4,1,3] (makes 11 cyclic shift, or any number that has a remainder of 11 when divided by 33);
- a=[4,2,5,1,3]a=[4,2,5,1,3] (makes 22 cyclic shifts, or any number that has a remainder of 22 when divided by 33).
Let's look at an example. Let n=6n=6, i.e. initially a=[1,2,3,4,5,6]a=[1,2,3,4,5,6]. A possible scenario is described below.
- i=1i=1: no matter how many cyclic shifts Petya makes, the array aa does not change.
- i=2i=2: let's say Petya decided to make a 11 cyclic shift, then the array will look like a=[2,1,3,4,5,6]a=[2,1,3,4,5,6].
- i=3i=3: let's say Petya decided to make 11 cyclic shift, then the array will look like a=[3,2,1,4,5,6]a=[3,2,1,4,5,6].
- i=4i=4: let's say Petya decided to make 22 cyclic shifts, the original array will look like a=[1,4,3,2,5,6]a=[1,4,3,2,5,6].
- i=5i=5: let's say Petya decided to make 00 cyclic shifts, then the array won't change.
- i=6i=6: let's say Petya decided to make 44 cyclic shifts, the array will look like a=[3,2,5,6,1,4]a=[3,2,5,6,1,4].
You are given a final array state aa after all nn operations. Determine if there is a way to perform the operation that produces this result. In this case, if an answer exists, print the numbers of cyclical shifts that occurred during each of the nn operations.
Input
The first line of the input contains an integer tt (1≤t≤5001≤t≤500) — the number of test cases in the test.
The descriptions of the test cases follow.
The first line of the description of each test case contains one integer nn (2≤n≤2?1032≤n≤2?103) — the length of the array aa.
The next line contains the final state of the array aa: nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n) are written. All aiai are distinct.
It is guaranteed that the sum of nn values over all test cases does not exceed 2?1032?103.
Output
For each test case, print the answer on a separate line.
Print -1 if the given final value aa cannot be obtained by performing an arbitrary number of cyclic shifts on each operation. Otherwise, print nn non-negative integers d1,d2,…,dnd1,d2,…,dn (di≥0di≥0), where didi means that during the ii-th operation the first ii elements of the array were cyclic shifted to the right didi times.
If there are several possible answers, print the one where the total number of shifts is minimal (that is, the sum of didi values is the smallest). If there are several such answers, print any of them.
Example
input
Copy
3 6 3 2 5 6 1 4 3 3 1 2 8 5 8 1 3 2 6 4 7
output
Copy
0 1 1 2 0 4 0 0 1 0 1 2 0 2 5 6 2
Note
The first test case matches the example from the statement.
The second set of input data is simple. Note that the answer [3,2,1][3,2,1] also gives the same permutation, but since the total number of shifts 3+2+13+2+1 is greater than 0+0+10+0+1, this answer is not correct.
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define end '\n'
using namespace std;
const int N = 2e3 + 10;
int T;
int n;
int a[N], b[N];
int d[N];void print()
{for (int i = 1; i <= n; ++i){cout << a[i] << ' ';}cout << endl;
}int main()
{IOS; cin.tie(0), cout.tie(0);cin >> T;while (T--){cin >> n;for (int i = 1; i <= n; ++i){cin >> a[i];} int cnt = 0;int ntemp = n;int pos, ans;for (int i = n; i >= 1; --i){ans = 0;for (int j = 1; j <= ntemp; ++j){if (a[j] == i){pos = j;break;}}if (pos == i){d[++cnt] = ans; }else if (pos != i){ans = ntemp - (i - pos);d[++cnt] = ans;}for (int j = 1; j <= ntemp; ++j){b[j] = a[j];}int idx = 0;for (int j = pos + 1; j <= ntemp; ++j){a[++idx] = b[j];}for (int j = 1; j <= pos; ++j){a[++idx] = b[j];}ntemp--;
// cout << "i: " << i << endl;
// cout << ans << endl;
// print();}for (int i = cnt; i >= 1; --i){cout << d[i];if (i != 1)cout << ' ';}cout << endl;}return 0;
}