题目背景

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

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

题目描述

议会由 $N$ 人组成，编号为 $0$ 到 $N-1$。在投票过程中，每人应该投恰好一票，但是其中某个人犯了个错误，投了两票！当某位成员投票时，他 / 她会在签名表上签一个名。签名表由一个长度为 $N+1$ 的序列 $A_0,A_1,\ldots,A_N(0\le A_i<N)$，其中有恰好一个元素出现了两次，其余元素恰好出现一次。

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

• 给定一个下标集合 $S$ 和一个值 $x$，可以得知是否存在 $i\in S$ 满足 $A_i=x$。

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

实现方式

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

你需要实现如下函数：

int delibera(int N);

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

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

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

• 集合 $S$ 中的元素需要在范围 $[0,N]$ 内且互不相等。
• $x$：表示询问的目标元素，满足 $0\le x<N$。
• 函数返回 true 当且仅当存在 $i\in S$ 使得 $A_i=x$，否则返回 false。
• 该函数最多可以被调用 $10^4$ 次。

输入格式

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

• 第 $1$ 行：一个整数 $T$，表示测试数据组数。即，函数 delibera 将会被调用 $T$ 次。
• 接下来 $T$ 组测试数据，每组测试数据的输入格式如下：
  • 第 $1$ 行：一个整数 $N$。
  • 第 $2$ 行：$N+1$ 个整数 $A_0,A_1,\ldots,A_N$。

输出格式

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

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

提示

【样例交互】

评测程序	选手程序
delibera(5)
	chiedi({0, 1, 2}, 3)
true
	chiedi({5}, 1)
false
	chiedi({4}, 3)
true
	return 3
Correct. 3 queries.

【样例解释】

在样例中，$N=5$，隐藏的数组 $A=[4,1,3,0,3,2]$。请注意样例并不满足数据范围中的 $N=99$。一种合法的询问序列为：

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

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

【数据范围】

• $T=50$；
• $N=99$；
• $0\le A_i<N(0\le i\le N)$；
• $A$ 中有恰好一个元素出现了两次，其余元素恰好出现一次。

【子任务 & 评分细则】

子任务编号	分值	约束条件
$0$		样例
$1$	$100$	$N=99$

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

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

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

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

$Q$	得分
$10^4$	$5$
$1500$	$10$
$625$	$20$
$400$	$55$
$300$	$75$
$260$	$100$

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