#USACOC2222C. Tests for Haybales

Tests for Haybales

题目描述

Farmer John 的奶牛们决定为 Farmer Nhoj 农场的奶牛们举办一场编程竞赛。为了使问题尽可能有趣,他们花费了大量时间来构造具有挑战性的测试用例。特别是对于一个问题,「Haybales」,奶牛们需要你的帮助来设计具有挑战性的测试用例。这有关解决以下这个有些奇妙的问题:

有一个有序整数数组 x1x2xNx_1 \leq x_2 \leq \dotsb \leq x_N,和一个整数 KK。你不知道这个数组以及 KK,但你知道对于每个索引 ii 使得 xjixi+Kx_{j_i} \leq x_i + K 的最大索引 jij_i。保证有 ijii\le j_i 以及 j1j2jNNj_1\le j_2\le \cdots \le j_N\le N

给定这些信息,Farmer John 的奶牛需要构造任意一个数组以及整数 KK 与该信息一致。构造需要满足对于所有 ii0xi10180 \leq x_i \leq 10^{18},并且 1K10181 \leq K \leq 10^{18}

可以证明这一定是可行的。请帮助 Farmer John 的奶牛们解决这一问题!

  • 1N1051 \leq N \leq 10^5

输入格式

输入的第一行包含 NN。第二行包含 j1,j2,,jNj_1,j_2,\ldots,j_N

输出格式

输出 KK,然后在下一行输出 x1,,xNx_1,\ldots,x_N。任何合法的输出均正确。

6
2 2 4 5 6 6
6
2 2 4 5 6 6

测试点性质

  • 所有测试点的 50% 满足 N5000N\le 5000
  • 其余测试点没有额外限制。

题目提供者

供题:Danny Mittal