You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

这是一道通信题。交互库从 $1$ 到 $n$ 中选定了一个整数，你需要找出它。你提交的同一份程序会在每个测试点上从头启动两次，两次运行之间不保留内存中的状态。

第一次运行时，你得到 $n$，可以向交互库输出猜测。交互库会返回所选整数与该猜测的大小关系。

第二次运行时，你会得到 $n$ 以及第一次运行中交互库给出的全部回答，但不会得到当时的猜测值。你需要仅根据这些信息输出所选整数。

第一次运行

首先从标准输入读取：

• 第一行为整数 1；
• 第二行为整数 $n$（$1\le n\le 10^9$）。

此后，每次向标准输出打印一个整数作为猜测，再从标准输入读取：

• 1：所选整数大于上一次猜测；
• -1：所选整数小于上一次猜测；
• 0：猜测正确。读到 0 后程序必须结束。

最多可以猜测 $30$ 次。每次输出猜测后必须换行并刷新输出缓冲区。

第二次运行

从标准输入读取：

• 第一行为整数 2；
• 第二行为整数 $n$；
• 第三行为第一次运行的猜测次数 $q$（$1\le q\le 30$）；
• 第四行为 $q$ 个整数 $a_1,a_2,\ldots,a_q$，即第一次运行中交互库依次给出的回答。保证 $a_q=0$。

输出一行，包含交互库选定的整数，然后结束程序。

两次运行的时间限制均为 $1$ 秒，内存限制均为 $1024$ MB。

交互示例

第一次运行：

1
5
-1
1
0

3
1
2

第二次运行：

2
5
3
-1 1 0

2

示例的互动过程中不需要输出额外的空行。

参考实现

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define sc second
#define ll long long
using namespace std;
int n, res, op, len; 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> op;
	if (op == 1)
	{
		cin >> n;
		int l = 1, r = n, mid, x;
		while (l <= r)
		{
			mid = (l + r) >> 1;
			cout << mid << endl;
			cin >> x;
			if (x == 0) return 0;
			if (x == 1) l = mid + 1;
			else r = mid - 1; 
		}	
	}
	else
	{
		cin >> n;
		int l = 1, r = n, mid, x;
		cin >> len;
		while (l <= r)
		{
			mid = (l + r) >> 1;
			cin >> x;
			if (x == 0) break;
			if (x == 1) l = mid + 1;
			else r = mid - 1; 
		}
		cout << mid << endl;
	}
	return 0;
}