33OJ
登录 注册

#P17764. 「LDOI R2」极差 / Range

    ID: 20377 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及− 上传者: 标签>洛谷原创Special JudgeO2优化构造洛谷月赛

「LDOI R2」极差 / Range

Problem Description

Define the range of a sequence as the maximum value in the sequence minus the minimum value in the sequence.

You need to construct two permutations a,ba,b of length nn such that every subinterval of aa of length greater than 11 has range greater than 11, every subinterval of bb of length greater than 11 has range greater than 11, and for each position ii, the absolute difference between aia_i and bib_i is greater than 11.

Formally, it must satisfy the following conditions:

  • ∀1≤l<r≤n\forall1 \le l < r \le n, max⁡i=lrai−min⁡i=lrai>1\max_{i=l}^r a_i - \min_{i=l}^r a_i > 1.

  • ∀1≤l<r≤n\forall1 \le l < r \le n, max⁡i=lrbi−min⁡i=lrbi>1\max_{i=l}^r b_i - \min_{i=l}^r b_i > 1.

  • ∀1≤i≤n\forall1 \le i \le n, ∣ai−bi∣>1|a_i - b_i| > 1.

If no such permutations exist, output −1-1.

Input Format

The input consists of a single positive integer nn.

Output Format

If no such permutations exist, output −1-1.

Otherwise, output two lines, each containing nn positive integers representing permutations aa and bb.

6

4 6 1 3 5 2
2 4 6 1 3 5

15
1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 
3 5 7 9 11 13 15 1 4 6 8 10 12 14 2 

Hint

Constraints

This problem uses subtask scoring, and subtask dependency is enabled.

Subtask n≤n \le Score Dependencies
11 99 3030 None
22 10310^3 11
33 10610^6 4040 1,21,2

For all test cases, 1≤n≤1061 \le n \le 10^6.