Interactive Problems

Your program talks to the judge instead of reading a fixed file. The rules are few but unforgiving.

The three rules

1. Flush after every output. Otherwise your query sits in a buffer, the judge waits, and you get Idleness Limit Exceeded.
2. Never cin.tie(nullptr). That optimisation is exactly what breaks interaction.
3. Count your queries. The limit is part of the problem, and exceeding it is a wrong answer, not a TLE.

int main() {
    ios::sync_with_stdio(false);
    // NO cin.tie(nullptr) here
    int n; cin >> n;
    ...
}

Flushing

cout << "? " << x << endl;          // endl flushes -- here it is CORRECT
// or
cout << "? " << x << "\n" << flush;
printf("? %d\n", x); fflush(stdout);

Interactive problems are the one place endl is the right choice.

The shape of a solution

int ask(int l, int r) {
    cout << "? " << l << " " << r << endl;
    int res; cin >> res;
    if (res == -1) exit(0);          // judge signalled an error: stop immediately
    return res;
}
 
void answer(int x) {
    cout << "! " << x << endl;
}

Exit on $-1$

Most judges send $-1$ after an invalid or excessive query. If you keep querying, the verdict becomes Idleness or a runtime error instead of the wrong answer you would otherwise see — which makes it much harder to diagnose.

The query budget tells you the algorithm

Budget	Intended technique
$\lceil {\log }_{2}n\rceil$	binary search
$2\log n$	binary search with a verification step, or a parallel search
$n$	ask about each element once
$n\log n$	a comparison sort using the queries as comparisons
$\sqrt{n}$	block decomposition
$O(1)$	a closed-form or algebraic identity
${\log }^{2}n$	nested binary searches, or binary search on a tree

The limit is the strongest hint in the statement. Read it before designing anything.

Adaptive judges

Many interactors are adaptive: they do not fix the hidden answer in advance, but choose it to remain consistent with everything said so far while making your life hardest. Consequences:

• Randomised strategies lose their guarantee — the judge sees your queries, not your coin flips, but it can still steer.
• Any argument of the form “on average this works” is unsafe; you need a worst-case bound.
• The right framing is adversary arguments: think about what information each query pins down, and ensure the answer space shrinks by a guaranteed factor.

Testing locally

Write your own interactor and pipe both ways:

// interactor.cpp: reads queries on stdin, replies on stdout, knows the hidden answer

mkfifo p1 p2
./main < p1 > p2 &
./interactor < p2 > p1

Simpler and usually sufficient: make the interactor a function inside your own solution, guarded by #ifdef LOCAL, so ask() calls it directly instead of touching the streams. That tests all your logic without process plumbing.

#ifdef LOCAL
int hidden = 42, queries = 0;
int ask(int x) { queries++; assert(queries <= LIMIT); return hidden < x ? -1 : hidden > x; }
#else
int ask(int x) { cout << "? " << x << endl; int r; cin >> r; return r; }
#endif

Common failure modes

Symptom	Cause
Idleness Limit Exceeded	not flushing, or cin.tie(nullptr)
Wrong Answer immediately	wrong query format — check spacing and the ?/! prefixes
Wrong Answer late	exceeded the query limit, or an off-by-one in the search bounds
Runtime error	kept reading after the judge sent $-1$
Works locally, fails on the judge	your local interactor is not adaptive

See also: Binary Search · Debugging · Contest Template