luogu#P10830. [COTS/CETS 2023] 平均数 Prosjek

    ID: 529 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2023Special JudgeO2优化CEOI(中欧)COCI(克罗地亚)

[COTS/CETS 2023] 平均数 Prosjek

题目背景

译自 Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection) D1T2。3s,0.5G\texttt{3s,0.5G}

祝 NaCly_Fish 生日快乐!(2024.7.28)

交互库好像出锅了 qwqwq。修复中。

UPD:感谢 @Rainbow_qwq 修复交互库。警示后人:慎用 multiset.count。

题目描述

在黑板上有 NN 个非负整数。在一次操作中,可以选择黑板上的两个整数 a,ba,b 满足 2(a+b)2\mid (a+b),将 a,ba,b 从黑板上擦去,然后写下 a+b2\dfrac{a+b}{2}。注意到每次操作后,黑板上的数都是整数。

试判断是否能让黑板上只剩下一个数。如果可以的话,还需要给出一组解。

输入格式

本题单个测试点内有多组测试数据。

第一行,一个正整数 TT,代表数据组数。

接下来依次描述 TT 组数据。

对于每组数据,第一行,一个正整数 NN,代表黑板上数的数量。

第二行,NN 个非负整数,描述黑板上的数。

输出格式

对于每组数据,输出若干行。

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

否则,输出 (N1)(N-1) 行,每行两个整数,表示每次要擦除的数。你需要保证操作的数是存在的,且它们的和能被 22 整除。

2
3
1 4 5
4
1 4 5 5
-1
1 5
3 5
4 4
1
6
1 2 3 4 5 6
1 5
3 3
4 6
3 5
2 4

提示

样例解释

样例 22 解释:$[\boldsymbol{\textcolor{red}{1}},2,3,4,\boldsymbol{\textcolor{red}{5}},6] \to [\boldsymbol{\textcolor{red}{3}},2,\boldsymbol{\textcolor{red}{3}},4,6]\to [3,2,\boldsymbol{\textcolor{red}{4}},\boldsymbol{\textcolor{red}{6}}]\to [\boldsymbol{\textcolor{red}{5}},\boldsymbol{\textcolor{red}{3}},2]\to [\boldsymbol{\textcolor{red}{4}},\boldsymbol{\textcolor{red}{2}}]\to [3]$。

数据范围

对于 100%100\% 的数据,保证:

  • 1T1051\le T\le 10^5
  • 1N,N1061\le N,\sum N\le 10^6
  • 0ai10180\le a_i\le 10^{18}
子任务编号 分值 约束
11 99 T100T\le 100N7N\le 7
22 2323 T100T\le 100ai10a_i\le 10
33 1616 aia_i 都为偶数
44 5252 无额外约束