DMOPC '17 Contest 4 P4 - Cops and Robbers - Olympiads Online Judge

DMOPC '17 Contest 4 P4 - Cops and Robbers

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

In the beautiful capital of Dmojistan, there are $N$ $N$ banks and a single policeman. The banks are numbered from $1$ $1$ to $N$ $N$ . You managed to find the policeman's schedule for the next $N$ $N$ days. It turns out that on the $i^\text{th}$ $i^{th}$ day, he will be protecting bank $a_i$ $a_{i}$ .

Armed with this information, you are planning to rob all $N$ $N$ banks in the next $N$ $N$ days. You will rob bank $b_i$ $b_{i}$ on the $i^\text{th}$ $i^{th}$ day. A robbery will be successful if the cop is not protecting that bank on that day (that is, $a_i \ne b_i$ $a_{i} \neq b_{i}$ ).

Before you can start robbing, you need to determine a sequence $b$ $b$ which will work. Output a sequence $b$ $b$ which will rob all $N$ $N$ banks or $-1$ $- 1$ if it is not possible to rob all $N$ $N$ banks. The sequence should be $N$ $N$ integers from $1$ $1$ to $N$ $N$ .

Any valid sequence will be accepted.

Constraints

$1 \le a_i \le N$ $1 \leq a_{i} \leq N$

Subtask 1 [50%]

$1 \le N \le 10^3$ $1 \leq N \leq 10^{3}$

Subtask 2 [50%]

$1 \le N \le 10^6$ $1 \leq N \leq 10^{6}$

Input Specification

The first line will contain $N$ $N$ .
The next line will contain $N$ $N$ space-separated integers $a_1, a_2, \dots, a_N$ $a_{1}, a_{2}, \dots, a_{N}$ .

Output Specification

Output a valid sequence $b$ $b$ if it is possible or $-1$ $- 1$ if it is not. The sequence $b$ $b$ should be $N$ $N$ integers from $1$ $1$ to $N$ $N$ .

Sample Input

Copy

5
2 1 1 1 1

Sample Output

Copy

1 2 3 4 5

Comments

2

AlanCCCL2S18 commented on June 4, 2018, 3:25 p.m.

I don't know what's getting me tle on the second subtask. Any ideas as to why this is happening?

5

wleung_bvg commented on June 4, 2018, 4:52 p.m. ← edited →

Your algorithm appears to be $\mathcal{O}(N^2)$ $O (N^{2})$ (due to ArrayDeque.contains()).

2

AlanCCCL2S18 commented on June 4, 2018, 6:58 p.m.

Thanks for the feedback :)