DMOPC '22 Contest 2 P3 - Good Permutations - Olympiads Online Judge

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 \leq i \leq 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 \leq N \leq 5 \times 10^{5}$

$1 \le T_i \le N$ $1 \leq T_{i} \leq 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 \leq N \leq 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

Copy

4
2 1 3 4

Sample Output

Copy

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