#HTR001D. 止战之殇

止战之殇

题目背景

孩子们眼中的希望 是什么形状
是否醒来有面包当早餐 再喝碗热汤
农夫被烧毁土地跟村庄 终于拿起枪
她却慢慢习惯放弃了抵抗
孩子们眼中的希望 是什么形状
是否院子有秋千可以荡 口袋里有糖
刺刀的光被仇恨所擦亮 在远方野蛮
而她却微笑着不知道慌张
——《止战之殇》

题目描述

nn 个因为战争而历尽苦难的孩子,他们想要终止野蛮的战争。他们每人要选定一个整数作为自己的 天真值,第 ii 个孩子的 天真值aia_i天真值 可以为负数。然后他们每次会选择两个孩子 x,yx,y 一起进行一次值为正整数 kk祈祷,直到每人都进行了 n1n-1祈祷。一次由两个 天真值 分别为 axa_xaya_y 的孩子一起进行一次值为 kk祈祷 能够产生两个值分别为 ax+ka_x+kay+ka_y+k殇歌。显然进行完所有 祈祷 后会产生 n(n1)n(n-1)殇歌。如果这些 殇歌 的值 恰好11n(n1)n(n-1) 的正整数 各一个,那么整个过程为一次 止战之殇,可以终止血腥的战争。现在孩子们想要知道他们怎样选择自己的 天真值 和每次 祈祷 的值才能制造出 止战之殇,由于他们还太小,所以就请你帮助他们。

题意简述

给定 nn,构造一个长度为 nn 的整数列 a1,a2,,ana_1,a_2,\dots,a_nn(n1)2\dfrac{n(n-1)}{2} 个三元组 xi,yi,ki(xiyi,kiZ+)x_i,y_i,k_i(x_i \neq y_i,k_i \in \mathbb{Z_+}),使得 i{1,2,,n},j=1n(n1)2([xj==i]+[yj==i])=n1\forall i \in \{1,2,\dots,n\},\sum_{j=1}^{\frac{n(n-1)}{2}}([x_j==i]+[y_j==i])=n-1{axi+ki:i=1,2,,n(n1)2}{ayi+ki:i=1,2,,n(n1)2}={1,2,,n(n1)}\left\{a_{x_i}+k_i:i=1,2,\dots,\frac{n(n-1)}{2}\right\}\cup\left\{a_{y_i}+k_i:i=1,2,\dots,\frac{n(n-1)}{2}\right\}=\{1,2,\dots,n(n-1)\}

输入格式

一行 33 个整数 n,op1,op2n,op1,op2

如果 op1=1op1=1,那么必须满足每一对 1x<yn1 \le x<y \le nx,yx,y 必须 恰好 一起进行一次 祈祷;否则没有特殊限制。

如果 op2=1op2=1,那么 天真值 必须为非负数;否则没有特殊限制。

输出格式

如果有解,第一行输出 nn;否则输出 1-1

如果有解,第二行输出 nn 个非负整数表示编号为 11nn 的孩子分别的 天真值,接下来 n(n1)2\dfrac{n(n-1)}{2} 行每行输出第 ii祈祷 选定的 x,y,kx,y,k

输入输出样例

1 0 0
1
1
2 0 0
2
0 -1
1 2 2
3 0 1
-1
4 1 1
4
5 2 0 3
1 3 7
1 4 1
2 4 7
2 1 6
4 3 2
3 2 1

说明/提示

样例解释

对于第一组样例,最后没有生成任何 殇歌,满足要求。

对于第二组样例,0+2=2,1+2=10+2=2,-1+2=1,恰好为 1122 各一个。

对于第三组样例,可以发现没有满足条件的方法。

对于第四组样例,有

5+7=12,0+7=7,5+1=6,3+1=4,2+7=9,3+7=10,5+7=12,0+7=7,5+1=6,3+1=4,2+7=9,3+7=10,

2+6=8,5+6=11,3+2=5,0+2=2,0+1=1,2+1=3,2+6=8,5+6=11,3+2=5,0+2=2,0+1=1,2+1=3,

恰好为 111212 各一个。


数据范围

本题共有 2020 个数据点,每个数据点 55 分,各个数据点的数据范围与限制如下。

Testdata No. nn \le op1op1 op2op2 特殊限制
141 \sim 4 300300 00 11 nn 为偶数
5105 \sim 10 nn 为奇数
111711 \sim 17 3×1033 \times 10^3 11
182018 \sim 20 77 00

对于 100%100\% 的数据,1n3×1031 \le n \le 3 \times 10^3op1,op2{0,1}op1,op2 \in \{0,1\}


提示

本题提供 Special Judge\texttt{Special Judge} 源码checker.exe,使用方法为:
命令行在目标文件夹输入指令:

checker.exe input.txt output.txt output.txt

其中 input.txt 是输入数据文件,output.txt 是程序运行结果文件。观察评判结果即可。

  • Accepted. 表示答案正确。
  • Misjudgment of the existence of the answer. 表示有解性判断不正确。
  • Negative ai. 表示 aia_i 为负数(op2=1op2=1 时)。
  • Invalid (x,y,k) No.i. 表示 xix_iyiy_i 不在 [1,n][1,n] 中或 xi=yix_i=y_ikik_i 不为正整数。
  • Invalid sum No.i. 表示 axi+kia_{x_i}+k_iayi+kia_{y_i}+k_i 不在 [1,n(n1)][1,n(n-1)] 中。
  • Sum No.i already appeared. 表示 axi+kia_{x_i}+k_iayi+kia_{y_i}+k_i 已经出现过。
  • (x,y) No.i already appeared. 表示 (xi,yi)(x_i,y_i) 已经出现过(op1=1op1=1 时)。

请务必保证输出格式正确,否则 Special Judge\texttt{Special Judge} 可能会返回 Unkown Error\texttt{Unkown Error} 等不可预估的结果。