#P12881. [COI 2025] 贪腐

    ID: 12067 传统题 1000ms 512MiB 尝试: 7 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTS递归构造二分图建模奇偶性分析不变量分析向下取整与向上取整回溯搜索可行性剪枝子集 DP

[COI 2025] 贪腐

题目描述

给定正整数 NN。初始时,集合 S={0,1,…,2N−1}S=\{0,1,\ldots,2^N-1\}。

初始时序列 b0=b1=…=bN−1=0b_0=b_1=\ldots=b_{N-1}=0。

考虑重复以下过程 2N−12^{N-1} 次:

  • 从 SS 中选出两个整数 X,YX,Y,满足 X⊕Y=2kX\oplus Y=2^k(k∈Nk\in \mathbb N)。将它们从 SS 中删去。
  • 令 bk←bk+1b_k\gets b_k+1。

给定序列 a0,a1,…,aN−1a_0,a_1,\ldots,a_{N-1}。判断是否能通过恰当地选择每次操作的 X,YX,Y,满足最终得到的 bb 序列和 aa 序列相同。如果能的话,还需要构造一组方案。

如果正确地判断了解的存在性,你也能得到部分分数。详见「计分方式」。

输入格式

第一行,正整数 NN。

第二行,NN 个非负整数 a0,a1,…,aN−1a_0,a_1,\ldots,a_{N-1}。

保证 ∑ai=2N−1\sum a_i=2^{N-1}。

输出格式

如果不可能,输出一行一个 -1\texttt{-1}。

否则,输出 2N−12^{N-1} 行,每行两个非负整数 X,YX,Y。

输出任意一组解均可。

输入输出样例 #1

输入 #1

2
2 0

输出 #1

0 1
2 3

输入输出样例 #2

输入 #2

2
1 1

输出 #2

-1

输入输出样例 #3

输入 #3

3
2 0 2

输出 #3

0 1
2 6
3 7
4 5

说明/提示

数据范围

  • 1≤N≤201\le N\le 20;
  • 0≤ai0\le a_i;
  • ∑ai=2N−1\sum a_i=2^{N-1}。

子任务

子任务 00 为样例。

子任务编号 NN 特殊性质 得分
11 ≤4\le 4 1515
22 ≥2\ge 2 对于所有 i>2i>2,ai=0a_i=0
33 ≤6\le 6 2020
44 ≤20\le 20 5050