# #H1040. find a hidden chain

ID: 95 Type: Interactive 1000ms 128MiB 尝试: 35 已通过: 3 难度: 4 上传者: 标签>算法基础二分交互题

# find a hidden chain

## 输出格式

4
1 2
2 3
1 4

3

2

3 2 3 4

2 3 4

! 3 4



## 数据规模与约定

$lim$ 表示交互次数上限。

• $\texttt{subtask1(15pts): n <= 20, lim = 20 }$
• $\texttt{subtask2(10pts): n = 100, lim = 50}$
• $\texttt{subtask3(15pts): n = 1000, lim = 200}$
• $\texttt{subtask4(19pts): n = 100000, lim = 60}$，保证树是一条链。
• $\texttt{subtask5(11pts): n = 100000, lim = 60}$，保证树是菊花图。
• $\texttt{subtask6(30pts): n = 100000, lim = 60}$

#include <bits/stdc++.h>
using namespace std;
int query(vector<int> &a) { // 传入你要询问的点，返回在链上的点的个数
printf("%d", (int)a.size());
for (vector<int>::iterator v = a.begin(); v != a.end(); v++) printf(" %d", *v);
putchar('\n');
fflush(stdout);
int d;
scanf("%d", &d);
return d;
}
int main() {
vector<int> a(2);
a[0]=1; a[1]=2;
int w=query(a),x=-1,y=-1;
if (w==2) x=1,y=2;
printf("! %d %d\n", x, y);
return 0;
}


$\texttt{idea: Lenstar, std: hydd, checker: Lenstar, data: Lenstar}$