File size: 1,746 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long k;
cin >> n >> k;
vector<vector<long long>> mat(n + 1, vector<long long>(n + 1, -1LL));
auto get = [&](int i, int j) -> long long {
if (mat[i][j] != -1LL) return mat[i][j];
cout << "QUERY " << i << " " << j << endl;
cout.flush();
long long v;
cin >> v;
mat[i][j] = v;
return v;
};
auto count_leq = [&](long long x) -> long long {
long long cnt = 0;
int i = 1, j = n;
while (i <= n && j >= 1) {
long long val = get(i, j);
if (val > x) {
j--;
} else {
cnt += j;
i++;
}
}
return cnt;
};
// Binary search for the row p
int lo = 1, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
bool in_first_mid;
if (mid == n) {
in_first_mid = true;
} else {
long long xx = get(mid + 1, 1) - 1;
long long s = count_leq(xx);
in_first_mid = (s >= k);
}
if (in_first_mid) {
hi = mid;
} else {
lo = mid + 1;
}
}
int p = lo;
// Binary search for the column q in row p
lo = 1, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
long long xx = get(p, mid);
long long s = count_leq(xx);
if (s >= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
int q = lo;
long long ans = get(p, q);
cout << "DONE " << ans << endl;
cout.flush();
return 0;
} |