137 lines
3.0 KiB
C++
137 lines
3.0 KiB
C++
#include <bits/stdc++.h>
|
|
|
|
#define FOR(i, n) for(lli i = 0; i < (lli)(n); ++i)
|
|
#define ALL(x) (x).begin(), (x).end()
|
|
|
|
#define X(A) get<0>(A)
|
|
#define Y(A) get<1>(A)
|
|
#define Z(A) get<2>(A)
|
|
#define W(A) get<3>(A)
|
|
|
|
#define mt make_tuple
|
|
#define mp make_pair
|
|
|
|
using namespace std;
|
|
using lli = long long int;
|
|
|
|
using pii = pair<lli, lli>;
|
|
using piii = tuple<lli, lli, lli>;
|
|
using vi = vector<lli>;
|
|
using vii = vector<pii>;
|
|
using viii = vector<piii>;
|
|
using vvi = vector<vi>;
|
|
using vvii = vector<vii>;
|
|
using vviii = vector<viii>;
|
|
using vb = vector<bool>;
|
|
using vvb = vector<vb>;
|
|
|
|
const int BOUND = 1000*1000;
|
|
//const int BOUND = 5;
|
|
int nbChairs;
|
|
|
|
int ask(int x, int y) {
|
|
printf("? %d %d\n", x, y);
|
|
fflush(stdout);
|
|
int out;
|
|
scanf("%d", &out);
|
|
return out;
|
|
}
|
|
|
|
struct Query {
|
|
unordered_map<int, int> memo;
|
|
|
|
int query(int v) {
|
|
if(memo.find(v) != memo.end())
|
|
return memo[v];
|
|
memo[v] = int_query(v);
|
|
return memo[v];
|
|
}
|
|
virtual int int_query(int v) = 0;
|
|
};
|
|
|
|
struct RowQuery: public Query {
|
|
int int_query(int v) {
|
|
return ask(BOUND + 42, v);
|
|
}
|
|
};
|
|
|
|
struct ColQuery: public Query {
|
|
int int_query(int v) {
|
|
return ask(v, BOUND + 42);
|
|
}
|
|
};
|
|
|
|
struct FindQuery: public Query {
|
|
vector<int> rows, cols;
|
|
vii prev;
|
|
vector<int> numInRow;
|
|
int cRow, foundThisRow;
|
|
FindQuery(): cRow(0), foundThisRow(0) {}
|
|
|
|
int int_query(int v) {
|
|
assert(v < (int)cols.size());
|
|
int ans = ask(cols[v], rows[cRow]);
|
|
for(const pii& p: prev)
|
|
if(p.second <= v && p.first < cRow)
|
|
ans--;
|
|
return ans;
|
|
}
|
|
void found(int col) {
|
|
prev.push_back(mp(cRow, col));
|
|
memo.clear();
|
|
foundThisRow++;
|
|
if(foundThisRow >= numInRow[cRow]) {
|
|
cRow++;
|
|
foundThisRow = 0;
|
|
}
|
|
}
|
|
void addRow(int v) {
|
|
if(rows.empty() || rows.back() != v) {
|
|
rows.push_back(v);
|
|
numInRow.push_back(1);
|
|
}
|
|
else
|
|
numInRow.back()++;
|
|
//printf("* Row %d (%d th)\n", v, numInRow.back());
|
|
}
|
|
void addCol(int v) {
|
|
if(cols.empty() || cols.back() != v)
|
|
cols.push_back(v);
|
|
//printf("* Col %d\n", v);
|
|
}
|
|
};
|
|
|
|
int dicho(Query* qu, int beg, int end, int seek) {
|
|
if(end - beg == 1)
|
|
return beg;
|
|
int m = (beg + end) / 2 - 1;
|
|
int mVal = qu->query(m);
|
|
if(mVal >= seek)
|
|
return dicho(qu, beg, m+1, seek);
|
|
return dicho(qu, m+1, end, seek);
|
|
}
|
|
|
|
int main(void) {
|
|
scanf("%d", &nbChairs);
|
|
|
|
FindQuery qFind;
|
|
RowQuery qRow;
|
|
ColQuery qCol;
|
|
|
|
FOR(i, nbChairs) {
|
|
qFind.addRow(dicho(&qRow, -BOUND, BOUND+1, i+1));
|
|
qFind.addCol(dicho(&qCol, -BOUND, BOUND+1, i+1));
|
|
}
|
|
|
|
FOR(i, nbChairs) {
|
|
int col = dicho(&qFind, 0, qFind.cols.size(), qFind.foundThisRow + 1);
|
|
qFind.found(col);
|
|
}
|
|
printf("!");
|
|
for(const pii& chair: qFind.prev)
|
|
printf(" %d %d", qFind.cols[chair.second], qFind.rows[chair.first]);
|
|
printf("\n");
|
|
fflush(stdout);
|
|
return 0;
|
|
}
|