#P17983. Redundancy Refrain
Redundancy Refrain
Redundancy Refrain
题目描述
给定长度为 的数组 ,每个元素属于 。你需要把每个 替换成 到 中的一个整数,非零元素必须保持不变,得到数组 。
如果存在两个不同的起点 ,使长度均为 的子数组
$$b_x,\ldots,b_{x+\ell-1}\quad\text{与}\quad b_y,\ldots,b_{y+\ell-1}$$包含完全相同的多重集合,即每个数在两段中的出现次数均相同,则称这两段形成一个长度为 的重复。两段允许重叠,且其中元素的排列顺序可以不同。
定义数组得分为所有这类重复的最大长度;没有重复时得分为 。请构造一个得分最小的补全数组。
输入格式
第一行一个整数 。每个用例占两行:
第一行两个整数 。
第二行 个整数 。
输出格式
每个用例输出一行 个整数 ,满足 ;若 ,必须有 。
输出任意一个达到最小得分的数组即可,无需输出得分。
数据范围
,,,。
所有用例的 之和不超过 。
样例
4
8 3
0 1 0 2 1 3 0 2
3 3
1 0 2
9 7
0 1 1 0 5 0 4 0 7
6 6
0 0 0 0 0 0
1 1 3 2 1 3 2 2
1 3 2
2 1 1 3 5 6 4 4 7
1 2 3 4 5 6