DMOPC '22 Contest 2 P3 - Good Permutations

Points: 12 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

Mr. Gregory recently discovered the existence of $\gcd$ ~\gcd~. Enthralled by its beauty, he challenges you to a puzzle. Mr. Gregory gives you a target permutation $T$ ~T~ of the integers $1, 2, \dots, N$ ~1, 2, \dots, N~. He tells you that a permutation $P$ ~P~ is good if it can be turned into $T$ ~T~ using the following operation any number of times: choose an integer $i$ ~i~ $(1 \le i \le N-1)$ ~(1 \le i \le N-1)~, such that $\gcd(P_i, P_{i+1}) = 1$ ~\gcd(P_i, P_{i+1}) = 1~, and swap elements $P_i$ ~P_i~ and $P_{i+1}$ ~P_{i+1}~. The answer to the puzzle is the lexicographically maximal good permutation $P$ ~P~.

Prove your worth by solving the puzzle!

Constraints

$1 \le N \le 5 \times 10^5$ ~1 \le N \le 5 \times 10^5~

$1 \le T_i \le N$ ~1 \le T_i \le N~

$T$ ~T~ is a permutation of the integers $1, 2, \dots, N$ ~1, 2, \dots, N~.

Subtask 1 [40%]

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

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains the integer $N$ ~N~.

The next line contains $N$ ~N~ space-separated integers, representing the target permutation $T$ ~T~.

Output Specification

Output $N$ ~N~ space-separated integers $P_1, P_2, \dots, P_N$ ~P_1, P_2, \dots, P_N~, the lexicographically maximal good permutation $P$ ~P~.

Sample Input

4
2 1 3 4

Sample Output

3 2 4 1

Comments

-2

YaoPlaysMC commented on Nov. 29, 2022, 6:58 p.m.

Why do I keep getting WA for my submission? I have no clue what I did wrong: https://dmoj.ca/src/5071271