#P5969. [Usaco2022 Jan] Tests for Haybales G

    ID: 4969 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>难度分类提高+/省选-构造与建模序列构造树算法DFS 序CF2400

[Usaco2022 Jan] Tests for Haybales G

题目描述

Farmer John 的奶牛要为一道名叫 Haybales 的竞赛题构造数据。设有一个非降的整数数组 x1≤x2≤⋯≤xNx_1\le x_2\le\cdots\le x_N 和一个整数 KK。对每个下标 ii,定义 jij_i 为使 xji≤xi+Kx_{j_i}\le x_i+K 成立的最大下标。

给定 j1,…,jNj_1,\ldots,j_N,构造任意一组数组和 KK,使它们符合上述关系。要求 0≤xi≤10180\le x_i\le10^{18}、1≤K≤10181\le K\le10^{18}。保证 i≤jii\le j_i、j1≤j2≤⋯≤jN≤Nj_1\le j_2\le\cdots\le j_N\le N,并且至少有一组解。

输入格式

第一行一个整数 NN(1≤N≤1051\le N\le10^5)。第二行 NN 个整数 j1,…,jNj_1,\ldots,j_N。

输出格式

第一行输出 KK,随后各用一行依次输出 x1,…,xNx_1,\ldots,x_N。当 ji=Nj_i=N 时,只需满足 xN≤xi+Kx_N\le x_i+K,没有下一个元素。若有多组可行解,任意输出一组。

样例 #1

样例输入 #1

6
2 2 4 5 6 6

样例输出 #1

6
1
6
17
22
27
32

样例解释 #1

样例取 K=6K=6,数组为 [1,6,17,22,27,32][1,6,17,22,27,32]。

ii xi+Kx_i+K 不大于该值的最后一个元素 下一个元素 jij_i
1 7 6 17 2
2 12
3 23 22 27 4
4 28 27 32 5
5 33 32 无 6
6 38

另一种合法输出是取 K=1K=1,数组为 [1,2,4,5,6,7][1,2,4,5,6,7]。

测试点性质

50%50\% 的输入满足 N≤5000N\le5000,其余输入无额外限制。