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

View as PDF

Submit solution

Points: 40 (partial)
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

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

Constraints

1 \le N \le 10^5

Subtask 1 [30%]

1 \le N \le 10^3

Subtask 2 [30%]

1 \le N \le 10^4

Subtask 3 [40%]

No additional constraints.

Input Specification

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

Output Specification

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

Sample Input 1

3

Sample Output 1

2 3 1

Explanation for Sample 1

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

Sample Input 2

6

Sample Output 2

3 6 1 4 2 5

Explanation for Sample 2

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


Comments


  • 4
    TechnobladeNeverDies  commented on Jan. 19, 2022, 7:32 p.m.

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