负责人

• 035966_L3

题目描述

现有一份二分查找代码（这份代码将在评测程序中实现，因此你无法查看其内容）。请编写一个自适应性的交互库，使得该代码的实际查找次数总是不小于理论上确保查找成功所需的最小查找次数。

交互方式

本题为交互题。

请使用以下模板：

#include <bits/stdc++.h>
using namespace std;
int respond(int n, int q, int x, vector<pair<int, int> > p)
{
	int z = 0;
	// ...
	return z;
}

• $n$：本次二分查找的上界。要查找的内容是一个不大于 $n$ 的正整数 $y$。
• $q$：本轮二分查找中已经完成的查找次数（不包括本次查找）。
• $x$：代表本次查找的基准值。你需要根据 $y$ 与 $x$ 的大小关系确定返回值 $z$：
  • 如果 $y>x$，返回 $z=0$。
  • 如果 $y=x$，返回 $z=1$。
  • 如果 $y<x$，返回 $z=2$。
  • 在不与任何先前的查找信息相矛盾的前提下，你可以动态修改 $y$ 的值。
• $p$：一个长度为 $q$ 的数组（下标从 $1$ 开始），表示本轮二分查找中先前的查找信息。它包含 $q$ 个二元组 $(u,v)$：
  • $u$ 表示评测程序在该次二分查找中传入的 $x$ 值。
  • $v$ 表示你的程序在该次二分查找中返回的 $z$ 值。
  • 保证数组中的查找信息是按照时间顺序从前往后排列的，没有经过打乱。
• 保证 $1 \le x,u \le n \le 10^4$，$1 \le q \le 35$，$v \in \{0,2\}$。
• 保证该函数被调用的次数不超过 $10^6$ 次。
• 保证所进行的二分查找轮数不超过 $4 \times 10^4$ 轮。

样例

下面的样例中一共进行了 $3$ 轮二分查找。

以下的交互过程可以获得 AC。