#214615. [OII 2025] 市政委员会 / Giunta comunale

译自 Italian Olympiad in Informatics (OII) 2025 - Giunta comunale。

重要的一天终于来了：市议会已将 OII 金字塔项目列入议程并进行审批。

议会由 人组成，编号为 到 。在投票过程中，每人应该投恰好一票，但是其中某个人犯了个错误，投了两票！当某位成员投票时，他 / 她会在签名表上签一个名。签名表由一个长度为 的序列 ，其中有恰好一个元素出现了两次，其余元素恰好出现一次。

遗憾的是，出于隐私原因，Nicoletta 无法直接查看签名表；但是她可以缴纳印花税来进行以下的查询：

• 给定一个下标集合 和一个值 ，可以得知是否存在 满足 。

帮助 Nicoletta 通过缴纳尽量少的印花税，确定哪个人签了两次名。你的得分取决于你缴纳的印花税数量。

实现方式

附件中包含一个实现示例 delibera.cpp。

你需要实现如下函数：

int delibera(int N);

• ：议会的人数。
• 该函数需要返回 中出现两次的元素。
• 对于每个测试点，该函数会被调用多次，请注意全局变量的清空问题。

你的函数可以调用如下函数来进行一次询问：

bool chiedi(vector<int> S, int x);

• 集合 中的元素需要在范围 内且互不相等。
• ：表示询问的目标元素，满足 。
• 函数返回 true 当且仅当存在 使得 ，否则返回 false。
• 该函数最多可以被调用 次。

评测程序的输入格式如下：

• 第 行：一个整数 ，表示测试数据组数。即，函数 delibera 将会被调用 次。
• 接下来 组测试数据，每组测试数据的输入格式如下：
  • 第 行：一个整数 。
  • 第 行： 个整数 。

评测程序的输出格式如下：

对于每组测试数据，输出你是否得出了正确的答案，以及你调用 chiedi 的次数。

【样例交互】

【样例解释】

在样例中，，隐藏的数组 。请注意样例并不满足数据范围中的 。一种合法的询问序列为：

• chiedi({0, 1, 2}, 3) true；
• chiedi({5}, 1) false；
• chiedi({4}, 3) true。

在 次询问后选手程序返回 ，表示在 中出现两次的元素。

【数据范围】

• ；
• ；
• ；
• 中有恰好一个元素出现了两次，其余元素恰好出现一次。

【子任务 & 评分细则】

对于每个子任务，你的得分为其中每组测试数据得分最小值。每组测试数据的得分规则如下：

如果出现如下情况，则该组数据得分为 ：

• 你返回的答案不正确；或
• 你至少对 chiedi 函数进行了一次不合法的调用；或
• 你对 chiedi 函数调用的次数过多（ 次）。

否则，该组测试数据的得分取决于你的询问次数 ：

如果你的 在表中两项之间，那么你的得分与 成线性关系。