DMOPC '17 Contest 4 P4 - Cops and Robbers

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

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

Armed with this information, you are planning to rob all N banks in the next N days. You will rob bank b_i on the 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).

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

Any valid sequence will be accepted.


1 \le a_i \le N

Subtask 1 [50%]

1 \le N \le 10^3

Subtask 2 [50%]

1 \le N \le 10^6

Input Specification

The first line will contain N.
The next line will contain N space-separated integers a_1, a_2, \dots, a_N.

Output Specification

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

Sample Input

2 1 1 1 1

Sample Output

1 2 3 4 5


  • 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) (due to ArrayDeque.contains()).

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

        Thanks for the feedback :)