DMOPC '21 Contest 5 P5 - Permutations & Primes (Hard Version) - Olympiads Online Judge

DMOPC '21 Contest 5 P5 - Permutations & Primes (Hard Version)

View as PDF

Submit solution

All submissions

Best submissions

Points: 40 (partial)

Time limit: 5.0s

Memory limit: 256M

Author:

4fecta

Problem type

The primeness of any permutation $p_1, p_2, \dots, p_N$ $p_{1}, p_{2}, \dots, p_{N}$ of $1, 2, \dots, N$ $1, 2, \dots, N$ is defined as the sum of all prime absolute differences of consecutive elements. Given an integer $N$ $N$ , find any permutation $p_1, p_2, \dots, p_N$ $p_{1}, p_{2}, \dots, p_{N}$ of $1, 2, \dots, N$ $1, 2, \dots, N$ with the maximum primeness over all length $N$ $N$ permutations.

Constraints

$1 \le N \le 10^5$ $1 \leq N \leq 10^{5}$

Subtask 1 [30%]

$1 \le N \le 10^3$ $1 \leq N \leq 10^{3}$

Subtask 2 [30%]

$1 \le N \le 10^4$ $1 \leq N \leq 10^{4}$

Subtask 3 [40%]

No additional constraints.

Input Specification

The first and only line of input contains a single integer $N$ $N$ .

Output Specification

Output $N$ $N$ space-separated integers on a single line, representing a permutation $p_1, p_2, \dots, p_N$ $p_{1}, p_{2}, \dots, p_{N}$ of $1, 2, \dots, N$ $1, 2, \dots, N$ with the maximum primeness over all length $N$ $N$ permutations.

Sample Input 1

Copy

Sample Output 1

Copy

2 3 1

Explanation for Sample 1

There are $2$ $2$ absolute differences of consecutive elements, namely $|2 - 3| = 1$ $| 2 - 3 | = 1$ and $|3 - 1| = 2$ $| 3 - 1 | = 2$ . Out of these, only $2$ $2$ is prime, so the primeness of this permutation is $2$ $2$ .

Sample Input 2

Copy

Sample Output 2

Copy

3 6 1 4 2 5

Explanation for Sample 2

The absolute differences of consecutive elements are $3, 5, 3, 2, 3$ $3, 5, 3, 2, 3$ . All of these are prime, so the primeness of this permutation is $3 + 5 + 3 + 2 + 3 = 16$ $3 + 5 + 3 + 2 + 3 = 16$ .

Comments

8

TechnobladeNeverDies commented on Jan. 20, 2022, 12:32 a.m.

petition to ban changes in problem constraints after a problem has at least one AC submission