DMOPC '21 Contest 9 P5 - Chika Circle

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Chika is playing a game!

Chika got her N friends arranged in a circle and gave them each a card labelled with a distinct number from 1 to N.

The game is to figure out who has which card. However, if you ask someone what card they have, they will instead reply with the minimum label of their neighbours' cards (for some reason). You have asked everyone for their answers and have recorded them in your array a.

Chika already knows the answers—because she cheated. You, however, must figure out the answer. It occurs to you that the answer is not always unique; that is, even if you ask everyone, there may be multiple valid configurations that are consistent with the answers.

As such, you decide to only declare a card's value when you are convinced of it, formally, when across all configurations consistent with the answers given, the person always has the same card.

In order to have the most fun, Chika has decreed that you will play T games and must answer for each.


1 \le T \le 10^6

3 \le N \le 10^6

1 \le a_i \le N

It is guaranteed that there is a valid arrangement of the integers from 1 to N that produce the array a.

The sum of N across all test cases will not exceed 10^6.

Subtask 1 [10%]

3 \le N \le 9

The sum of N across all test cases will not exceed 10^5.

Subtask 2 [30%]

The sum of N across all test cases will not exceed 2 \times 10^3.

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains the integer T.

The next 2T lines contain games. For each game, the first line contains the integer N, and the next line contains N integers a_i, the responses from Chika's friends.

Output Specification

For each game, output an array of length N, where the ith element is either the number on the card of the ith person or 0 if the number varies across valid configurations.

Sample Input

1 3 1 4 2
1 3 1 3

Sample Output

3 1 0 2 0
0 0 0 0


It can be proven that the only two valid configurations for the first game are 3 1 4 2 5 and 3 1 5 2 4.


There are no comments at the moment.