[COTS 2023] 平均数 Prosjek

Luogu

IDLGP10830

Time3000ms

Memory512MB

DifficultyP7

2023数论Special JudgeO2优化构造COTS（克罗地亚）

在黑板上有 $N$ 个非负整数。在一次操作中，可以选择黑板上的两个整数 $a,b$ 满足 $2\mid (a+b)$，将 $a,b$ 从黑板上擦去，然后写下 $(a+b)/2$。注意到每次操作后，黑板上的数都是整数。试判断是否能让黑板上只剩下一个数。如果可以的话，还需要给出一组解。 ## Input **本题单个测试点内有多组测试数据。** 第一行，一个正整数 $T$，代表数据组数。接下来依次描述 $T$ 组数据。对于每组数据，第一行，一个正整数 $N$，代表黑板上数的数量。第二行，$N$ 个非负整数，描述黑板上的数。 ## Output 对于每组数据，输出若干行。如果不可行，输出一行一个 $\texttt{-1}$；否则，输出 $(N-1)$ 行，每行两个整数，表示每次要擦除的数。你需要保证操作的数是存在的，且它们的和能被 $2$ 整除。 [samples] ## Background 译自 [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D1T2。$\texttt{3s,0.5G}$。祝 NaCly_Fish 生日快乐！（2024.7.28）感谢 @Rainbow_qwq 修复交互库。警示后人：慎用 `multiset.count`（复杂度可退化至线性）。 ## Note #### 样例解释样例 $2$ 解释：$[\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\%$ 的数据，保证： - $1\le T\le 10^5$； - $1\le N,\sum N\le 10^6$； - $0\le a_i\le 10^{18}$。 | 子任务编号 | 分值 | 约束 | |:-----:|:------:|:-------:| | $1$ | $9$ | $T\le 100$，$N\le 7$ | | $2$ | $23$ | $T\le 100$，$a_i\le 10$ | | $3$ | $16$ | $a_i$ 都为偶数 | | $4$ | $52$ | 无额外约束 |

Samples

Input #1

Output #1

Input #2

1
6
1 2 3 4 5 6

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[COTS 2023] 平均数 Prosjek",
    "description": {
      "content": " 在黑板上有 $N$ 个非负整数。在一次操作中，可以选择黑板上的两个整数 $a,b$ 满足 $2\\mid (a+b)$，将 $a,b$ 从黑板上擦去，然后写下 $(a+b)/2$。注意到每次操作后，黑板上的数都是整数。 试判断是否能让黑板上只剩下一个数。如果可以的话，还需要给出一组解。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10830"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在黑板上有 $N$ 个非负整数。在一次操作中，可以选择黑板上的两个整数 $a,b$ 满足 $2\\mid (a+b)$，将 $a,b$ 从黑板上擦去，然后写下 $(a+b)/2$。注意到每次操作后，黑板上的数都是整数。\n\n试判断是否能让黑板上只剩下一个数。如果可以的话，还需要给出一组解。\n\n## Input\n\n**本题单个测试点内有多组测试数据。**\n\n第一行，一个正整数 $T$，代表数据组数。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments