#P17215. [2025年国家集训队模拟赛]迷宫守卫

    ID: 16374 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高二分答案线性 DP一维差分滚动数组路径恢复

[2025年国家集训队模拟赛]迷宫守卫

迷宫守卫(maze)

题目描述

给出一个集合 SS,要求你将 SS 分成尽可能少的 kk 个子集,满足每个子集中的元素互不相同。

为了增强这道题的思维含量,每个子集的大小必须为偶数。

输入格式

第一行一个整数 TT 表示测试数据组数。

对于每组数据:第一行一个整数 nn 表示 SS 的元素个数;第二行 nn 个整数表示 SS 中的元素。

输出格式

对于每组数据,第一行输出一个整数 kk 表示你划分为了 kk 个子集。

接下来 kk 行,每行第一个整数 pp 表示这个子集的大小,你需要保证 pp 为偶数,接下来 pp 个数表示这个子集中的元素。

如果无解,输出一行一个 -1。

样例 1 输入

1
10
1 2 2 2 3 3 3 4 5 5

样例 1 输出

3
4 1 2 3 5
4 2 3 4 5
2 2 3

样例 2 输入

1
5
1 1 1 1 1

样例 2 输出

-1
     |

数据范围

对于 100%100\% 的数据,满足 1≤T≤1031\le T\le 10^3,1≤∑n≤1031\le\sum n\le 10^3,1≤Si≤1061\le S_i\le 10^6。

测试点编号 T≤T\le n≤n\le Si≤S_i\le 特殊性质
1~2 11 1010 10610^6 无
3~4 10310^3 22
5~6 1010 2020
7 10310^3 11
8~9 22
10~12 33
13~16 10610^6 A
17~18 B
19~22 10210^2 无
23~25 10310^3
  • 特殊性质 A:保证 SS 中的元素在范围内均匀随机生成。
  • 特殊性质 B:保证 SS 中的元素最多存在两个相同的元素。