PIB '20 P7 - Karnaugh Maps

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.5s
Memory limit: 128M

Author:
Problem types

You have a one-indexed array a of length N. This array is special: each value will occur at most K times in the array.

You also decided on a value d, where d > 1. You can then perform the following operation any number (possibly zero) of times:

  • Choose an index i (1 \le i \le N - d), and swap a_i with a_{i+d}.

Please output the lexicographically smallest array that can be made if you choose the optimal value of d. An array a is lexicographically smaller than an array b if there is some index i such that a_i < b_i and a_j = b_j for all j < i.

Input Specification

The first line will contain the integer N (1 \le N \le 5 \times 10^4).

The next line will contain N integers, a_i (1 \le a_i \le 10^9). It is guaranteed that each value of a_i will occur at most K times.

Output Specification

Output the lexicographically smallest array that can be made if the optimal value of d is chosen.

Subtasks

Subtask 1 [12%]

K = 1

Subtask 2 [27%]

K \le 4

Subtask 3 [61%]

K \le 500

Sample Input For Subtask 1

5
5 4 3 2 1

Sample Output For Subtask 1

1 2 3 4 5

Sample Input For Subtask 2

6
3 1 1 1 1 2

Sample Output For Subtask 2

1 1 1 1 3 2

Explanation For Sample For Subtask 2

One optimal value of d is 4.

Sample Input For Subtask 3

11
5 1 2 1 2 1 2 1 1 2 100

Sample Output For Subtask 3

1 1 1 1 2 5 2 2 1 2 100

Comments

There are no comments at the moment.