DMOPC '17 Contest 4 P4 - Cops and Robbers - DMOJ: Modern 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^\text{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^\text{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 \ne 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 \le a_i \le N~

Subtask 1 [50%]

$1 \le N \le 10^3$ ~1 \le N \le 10^3~

Subtask 2 [50%]

$1 \le N \le 10^6$ ~1 \le N \le 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

5
2 1 1 1 1

Sample Output

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)$ ~\mathcal{O}(N^2)~ (due to ArrayDeque.contains()).

2

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

Thanks for the feedback :)