Person in charge

• 035966_L3

Problem Description

We have a binary search implementation (whose code you cannot see as it's implemented in the judge). Your task is to write an adaptive interaction library that ensures the actual number of searches performed is never less than the theoretical minimum required to guarantee successful search.

Interaction Protocol

This is an interactive problem.

Use the following template:

#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;
}

Parameters:

• $n$: Upper bound for current binary search. The target is a positive integer $1 \le y \le n$.
• $q$: Number of searches already performed in this round (excluding current search).
• $x$: Current pivot value. Return $z$ based on $y$'s relation to $x$:
  • $z=0$ if $y > x$
  • $z=1$ if $y = x$
  • $z=2$ if $y < x$
  • You may dynamically modify $y$ as long as it doesn't contradict previous search information.
• $p$: Array of length $q$ (1-indexed) containing previous search info in this round:
  • Each pair $u,v$ represents:
    • $u$: $x$ value passed by judge
    • $v$: $z$ value returned by your program
  • Guaranteed to be in chronological order.

Constraints:

• $1 \le x,u \le n \le 10^4$
• $0 \le q \le 35$
• $v \in \{0,2\}$
• Function will be called at most $10^6$ times
• Total search rounds does not exceed $4 \times 10^4$

Sample

Three search rounds are shown below (AC solution):