Circular Permutation Recovery solution codechef
You are given two integerssuch that . Your friend is hiding from you a permutation of integers from to , whose elements are written cyclically.
Your friend doesn’t tell you the permutation. Instead, he tells you this. For eachfrom to he will tell you the number of such integers with such that .
Given, find any permutation producing them or tell that there is no such permutation.
Input Format Circular Permutation Recovery solution codechef
The first line of the input contains a single integerthe number of test cases. The description of test cases follows.
The first line of each test case contains two integers.
The second line of each test case containsintegers .
Output Format Circular Permutation Recovery solution codechef
For each test case, if there is no permutation producing array, output . Otherwise, output integers ( , for ) the required permutation. If there are several such permutations, you can output any.
- The sum of over all test cases doesn’t exceed
Subtask 1 (50 points): The sum ofover all test cases doesn’t exceed Subtask 2 (50 points): No additional constraints
Sample Input 1
2 5 3 1 2 1 3 0 5 3 3 0 0 0 1
Circular Permutation Recovery solution codechef Sample Output 1
3 4 2 5 1 -1
In the first test case,produces . Indeed, there is one element among smaller than , there are elements among smaller than , one element among smaller than , three elements among smaller than , and no elements among smaller than .
It can be shown that arrayfrom the second test case doesn’t correspond to any permutation.