Proficient.
Put your skills to the test.

Problem summary

An N×M ceiling has distinct signed 32-bit heights. Find any cell higher than all its side-adjacent neighbors, using at most 3050 height queries. You do not receive the height matrix directly: communicate with the interactive grader.

Source clarification. The official problem is interactive. The example fields reproduce the received initial dimensions/heights and emitted query/answer lines of the published dialogue; they are not a standalone batch test.

Constraints

1 ≤ N,M ≤ 1000; all heights distinct signed 32-bit integers; at most 3050 queries.

Worked example

An independently prepared example for this explanation.

3 2
3
4
1
7
6
2

0 0 0
0 1 0
0 2 0
0 0 1
0 1 1
0 2 1
1 0 1

Solution analysis

1. Keep an active rectangle and a known witness inside it whose height exceeds all cells on its discarded boundary. Split the longer dimension at its middle and query every cell of that separating row or column. Cache all queried heights.
2. If the witness is higher than the separator maximum, retain the half containing the witness without more queries. Otherwise the separator maximum is a new candidate. Only its two neighbors perpendicular to the separator can be higher: the neighbors along the separator are already no higher. If neither is higher, answer; otherwise retain the half containing a higher neighbor and make that neighbor the witness.
3. The official dialogue queries a 3×2 ceiling with rows (3,7),(4,6),(1,2), then reports (0,1), whose height 7 exceeds its neighbors 3 and 6. Our separator strategy can ask a different valid dialogue. Alternating splits of a 1000×1000 rectangle scan at most 2988 cells over at most 19 separators, plus at most two neighbor queries per separator: at most 3026 calls.

Why it works

The invariant is initially vacuous. If a witness beats the separator, its half retains a point higher than all discarded boundary cells. Otherwise a higher perpendicular neighbor beats both the separator maximum and the previous witness, so the same invariant holds in its half. If neither perpendicular neighbor is higher, separator neighbors and discarded-boundary neighbors are also lower, making the candidate a global-grid local maximum. Each recursion removes a middle line and at least half of the longer dimension, so termination follows.

Watch out. This requires the original interactive grader. Flush every query with endl and stop on failed input. Do not supply a plain height matrix as if this were a batch-input problem.

Requires an interactive judge implementing queries 0 x y and final answer 1 x y. The published dialogue is illustrative; query order may differ.

#include<cstdlib>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
    int n,m;
    if(!(cin>>n>>m)){
        return 0;
    }
    vector<vector<int>>height(n,vector<int>(m));
    vector<vector<bool>>known(n,vector<bool>(m,false));
    auto ask=[&](int x,int y){
        if(!known[x][y]){
            cout<<0<<' '<<x<<' '<<y<<endl;
            if(!(cin>>height[x][y])){
                exit(0);
            }
            known[x][y]=true;
        }
        return height[x][y];
    };
    int top=0,bottom=n-1,left=0,right=m-1;
    pair<int,int>witness={-1,-1};
    while(true){
        bool row=bottom-top>=right-left;
        int middle=row?(top+bottom)/2:(left+right)/2;
        pair<int,int>best=row?make_pair(middle,left):make_pair(top,middle);
        int start=row?left:top;
        int finish=row?right:bottom;
        for(int i=start;i<=finish;i++){
            pair<int,int>cell=row?make_pair(middle,i):make_pair(i,middle);
            if(ask(cell.first,cell.second)>ask(best.first,best.second)){
                best=cell;
            }
        }
        // A previous witness above the separator maximum already selects a half.
        if(witness.first<0||ask(best.first,best.second)>=ask(witness.first,witness.second)){
            pair<int,int>higher=best;
            for(int delta:{-1,1}){
                int x=best.first+(row?delta:0);
                int y=best.second+(row?0:delta);
                if(x>=top&&x<=bottom&&y>=left&&y<=right&&
                    ask(x,y)>ask(higher.first,higher.second)){
                    higher={x,y};
                }
            }
            if(higher==best){
                cout<<1<<' '<<best.first<<' '<<best.second<<endl;
                return 0;
            }
            witness=higher;
        }
        if(row){
            if(witness.first<middle){
                bottom=middle-1;
            }
            else{
                top=middle+1;
            }
        }
        else{
            if(witness.second<middle){
                right=middle-1;
            }
            else{
                left=middle+1;
            }
        }
    }
}