레이팅 미적용농부 존의 소들은 농부 뇨즈의 농장에 있는 소들을 위한 프로그래밍 대회를 열기로 했다. 문제를 최대한 재미있게 만들기 위해, 소들은 까다로운 입력 케이스를 만드는 데 상당한 시간을 쏟았다. 특히 "Haybales"라는 문제에서, 소들은 까다로운 입력을 만들기 위해 여러분의 도움이 필요하다. 이를 위해서는 다음의 다소 흥미로운 문제를 풀어야 한다.
정렬된 정수 배열 \(x_1 \leq x_2 \leq \dotsb \leq x_N\) (\(1 \leq N \leq 10^5\))과 정수 \(K\)가 있다. 배열과 \(K\)는 알 수 없지만, 각 인덱스 \(i\)에 대해 \(x_{j_i} \leq x_i + K\)를 만족하는 가장 큰 인덱스 \(j_i\)는 알고 있다. \(i\le j_i\)이고 \(j_1\le j_2\le \cdots \le j_N\le N\)임이 보장된다.
이 정보가 주어졌을 때, 농부 존의 소들은 이 정보와 일치하는 임의의 배열과 정수 \(K\)를 구성해야 한다. 구성한 답은 모든 \(i\)에 대해 \(0 \leq x_i \leq 10^{18}\)와 \(1 \leq K \leq 10^{18}\)를 만족해야 한다.
이것이 항상 가능함을 증명할 수 있다. 농부 존의 소들이 이 문제를 풀 수 있도록 도와주자!
출제자: Danny Mittal
배점
- 전체 입력의 50%에서 \(N\le 5000\)
- 나머지 입력에는 추가 제약이 없다.
출제자: Danny Mittal
첫째 줄에 \(N\)이 주어진다. 다음 줄에 \(j_1,j_2,\ldots,j_N\)이 주어진다.
\(K\)를 출력한 뒤, \(x_1,\ldots,x_N\)을 한 줄에 하나씩 출력한다. 조건을 만족하는 어떤 출력이든 정답으로 인정된다.
6
2 2 4 5 6 66
1
6
17
22
27
32The sample output is the array \(a = [1, 6, 17, 22, 27, 32]\) with \(K = 6\).
\(j_1 = 2\) is satisfied because \(a_2 = 6 \leq 1 + 6 = a_1 + K\) but
\(a_3 = 17 > 1 + 6 = a_1 + K\), so \(a_2\) is the largest element that is at most
\(a_1\). Similarly,
- \(j_2 = 2\) is satisfied because \(a_2 = 6 \leq 6 + 6\) but \(a_3 = 17 > 6 + 6\)
- \(j_3 = 4\) is satisfied because \(a_4 = 22 \leq 17 + 6\) but \(a_5 = 27 > 17 + 6\)
- \(j_4 = 5\) is satisfied because \(a_5 = 27 \leq 22 + 6\) but \(a_5 = 32 > 22 + 6\)
- \(j_5 = 6\) is satisfied because \(a_6 = 32 \leq 27 + 6\) and \(a_6\) is the last element of the array
- \(j_6 = 6\) is satisfied because \(a_6 = 32 \leq 32 + 6\) and \(a_6\) is the last element of the array
This is not the only possible correct output for the sample input. For example,
you could instead output the array \([1, 2, 4, 5, 6, 7]\) with \(K = 1\).