문제
N개의 양의 정수로 이루어진 수열 Hi가 주어진다.
H를 두 개의 수열 A와 B로 분할하여, A와 B 각각이 단조증가하는 등차수열이 되도록 하여라.
입력
1번 줄 : N(2 ≤ N ≤ 100,000)
2번 줄 : H1 H2 ... HN (1 ≤ Hi ≤ 1,000,000,000)
출력
1번 줄에는 수열 A의 길이를 출력하여라.
2번 줄에는 A1, A2, ... 를 공백으로 구분하여 출력하여라.
3번 줄에는 수열 B의 길이를 출력하여라.
4번 줄에는 B1, B2, ... 를 공백으로 구분하여 출력하여라.
A와 B는 각각 길이가 1 이상이어야 하며, H의 모든 원소는 A나 B에서 정확하게 한 번 등장하여야 한다.
- |A|, |B| ≥ 1
- |A| + |B| = N
- A1 ≤ A2 ≤ ...
- B1 ≤ B2 ≤ ...
- A2 - A1 = A3 - A2 = ...
- B2 - B1 = B3 - B2 = ...
여러 개의 답이 존재할 경우, 그 중 아무거나 출력하여라.
답이 존재하지 않을 경우, 첫 번째 줄에 "-1"(쌍따옴표 제외)를 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | N ≤ 15 |
| #2 | 30점 | N ≤ 300 |
| #3 | 30점 | N ≤ 100,000, A와 B의 길이가 같은 경우의 해가 존재한다. |
| #4 | 30점 | 문제의 조건 외에 주어진 제한이 없다. |
예제 #1
4
1 3 2 4
2
1 2
2
3 4
예제 #2
6
23 4 7 6 8 15
3
4 6 8
3
7 15 23
예제 #3
6
1 2 3 7 9 10
-1
힌트
출처
COCI '19 Contest 3 #3
로그인해야 코드를 작성할 수 있어요.