File size: 2,086 Bytes
14c9c2b | 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 77 78 79 80 | #include <bits/stdc++.h>
using namespace std;
static const long long UNKNOWN = LLONG_MIN;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long k;
if (!(cin >> n >> k)) return 0;
vector<vector<long long>> cache(n+1, vector<long long>(n+1, UNKNOWN));
long long query_count = 0;
const long long QUERY_LIMIT = 50000;
auto flush = [](){ cout.flush(); };
auto query = [&](int x, int y)->long long {
if (cache[x][y] != UNKNOWN) return cache[x][y];
if (query_count >= QUERY_LIMIT) {
// Fallback: should not happen; but to avoid further queries, return known edge
return cache[x][y] = 0;
}
cout << "QUERY " << x << " " << y << "\n";
flush();
long long v;
if (!(cin >> v)) {
// If read fails, set to 0
v = 0;
}
cache[x][y] = v;
++query_count;
return v;
};
auto count_leq = [&](long long mid)->long long {
long long cnt = 0;
int j = n;
for (int i = 1; i <= n; ++i) {
while (j >= 1) {
long long v = query(i, j);
if (v > mid) {
--j;
} else {
cnt += j;
break;
}
if (j == 0) break;
}
if (j == 0) break;
}
return cnt;
};
// Establish bounds
long long low = query(1,1);
long long high = query(n,n);
if (low > high) swap(low, high); // just in case
// Binary search for minimal value v such that count_leq(v) >= k
while (low < high) {
long long mid = low + ( (__int128)(high - low) / 2 );
long long cnt = count_leq(mid);
if (cnt >= k) {
high = mid;
} else {
low = mid + 1;
}
// Optional guard: if nearing query limit, break and use current high
if (query_count + 2*n > QUERY_LIMIT) break;
}
cout << "DONE " << high << "\n";
flush();
return 0;
} |