#PU1187. USACO 2022 January Contest, Gold — Problem 3. Tests for Haybales

    ID: 1493 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan22来源:usaco.orgscoring:equal_test_cases构造

USACO 2022 January Contest, Gold — Problem 3. Tests for Haybales

USACO 2022 January Contest, Gold — Problem 3. Tests for Haybales

题目描述

Farmer John's cows have decided to offer a programming contest for the cows on Farmer Nhoj's farm. In order to make the problems as fun as possible, they have spent considerable time coming up with challenging input cases. For one problem in particular, "Haybales", the cows need your help devising challenging inputs. This involve solving the following somewhat intriguing problem: There is an array of sorted integers x1≤x2≤⋯≤xNx_1 \leq x_2 \leq \dotsb \leq x_N (1≤N≤1051 \leq N \leq 10^5), and an integer KK. You don't know the array or KK, but you do know for each index ii, the largest index jij_i such that xji≤xi+Kx_{j_i} \leq x_i + K. It is guaranteed that i≤jii\le j_i and j1≤j2≤⋯≤jN≤Nj_1\le j_2\le \cdots \le j_N\le N. Given this information, Farmer John's cows need to construct any array along with some integer KK that matches that information. The construction needs to satisfy 0≤xi≤10180 \leq x_i \leq 10^{18} for all ii and 1≤K≤10181 \leq K \leq 10^{18}. It can be proven that this is always possible. Help Farmer John's cows solve this problem!

输入格式

The first line of input contains NN. The next line contains j1,j2,…,jNj_1,j_2,\ldots,j_N.

输出格式

Print KK, then x1,…,xNx_1,\ldots,x_N on separate lines. Any valid output will be accepted.

数据范围

For 50% of all inputs, N≤5000N\le 5000 For the remaining inputs, there are no additional constraints. Problem credits: Danny Mittal

样例

样例 1

6
2 2 4 5 6 6
6
1
6
17
22
27
32
The 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$.