Double Permutation

시간 제한1초메모리 제한1024 MB

요약

1부터 N까지 각 정수를 2행 N열 격자에 두 번씩 배치하되 x의 두 복사본 사이 맨해튼 거리가 정확히 x가 되도록 하고, 불가능하면 -1을 출력한다.

난이도: 보통10점 중 6점
유형: 구현, 그리디, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

양의 정수 $N$ 이 주어진다. 다음 조건을 만족하는 $2$ 행 $N$ 열의 격자를 구해보자.

각 칸에는 $1$ 이상 $N$ 이하의 정수 중 하나를 쓴다.
$1$ 이상 $N$ 이하의 모든 정수는 격자 전체에서 정확히 2번씩 등장해야 한다.
모든 정수 $x$ 에 대하여, 해당 숫자가 적힌 두 칸의 맨해튼 거리[1]가 정확히 $x$ 가 되어야 한다. $(1 \le x \le N)$

입력

첫 번째 줄에 정수 $N$ 이 주어진다.

출력

만약 조건을 만족하는 격자가 있다면 다음 $2$ 개의 줄에 걸쳐 각 줄에 $N$ 개의 정수를 공백으로 구분하여 출력한다. $i$ 번째 줄의 $j$ 번째 정수는 격자의 $i$ 행 $j$ 열에 적을 정수를 의미한다. 가능한 격자가 여러 개라면 그중 아무것이나 출력한다. $(1 \le i \le 2$ ; $1 \le j \le N)$

만약 조건을 만족하는 격자가 없다면 첫 번째 줄에 -1을 출력한다.

제한

$1 \le N \le 5\\,000$

힌트

[1] 격자의 $a$ 행 $b$ 열과 $c$ 행 $d$ 열의 맨해튼 거리는 $|a - c| + |b - d|$ 이다.

예제2

예제 1
입력
```
4
```
예상 출력
```
3 1 2 4
4 1 3 2
```
예제 2
입력
```
2
```
예상 출력
```
-1
```