题库练习 Find the Zero
← 上一题 下一题 →

A16868 | Find the Zero

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

这是一个交互题。

给定一个整数 $n$。存在一个长度为 $2n$ 的隐藏数组 $a$。从 $1$ 到 $n$ 的每个整数在 $a$ 中都恰好出现一次,其余元素均为 $0$。

你可以进行如下类型的查询:

- 选择两个整数 $i$ 和 $j$($1 \le i, j \le 2n$,$i \ne j$),裁判会回应 $1$,如果 $a_i = a_j$,否则回应 $0$。

请在不超过 $n+1$ 次查询内,找到任意一个满足 $a_k=0$ 的整数 $k$($1 \le k \le 2n$)。注意交互方是自适应的,这意味着隐藏数组 $a$ 可能会根据你的查询动态变化,但不会违反之前的查询结果。

输入格式

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$($1 \le t \le 10^3$)。接下来是各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$($2 \le n \le 10^4$)。隐藏数组 $a$ 的长度为 $2n$。

保证所有测试用例中 $n$ 的总和不超过 $10^4$。

输出格式

(交互题,无需输出格式固定说明。)

输入输出样例

输入 #1
2
2

0

1

3

1

0

0
输出 #1
? 1 2

? 3 1

! 3

? 5 6

? 2 4

? 1 3

! 6
C++ 编辑器
输入
输出