File size: 2,400 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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include <bits/stdc++.h>
using namespace std;
static const long long QUERY_LIMIT = 50000;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long k;
if (!(cin >> n >> k)) {
return 0;
}
auto query = [&](int x, int y) -> long long {
cout << "QUERY " << x << " " << y << "\n" << flush;
long long v;
cin >> v;
return v;
};
auto done = [&](long long ans) {
cout << "DONE " << ans << "\n" << flush;
// Do not read any further
// Exit
};
long long total = 1LL * n * n;
bool from_min = (k <= total - k + 1);
long long t = from_min ? k : (total - k + 1);
struct Node {
long long val;
int i, j;
};
if (from_min) {
// K-way merge from the start of each row
struct Cmp {
bool operator()(const Node& a, const Node& b) const {
return a.val > b.val;
}
};
priority_queue<Node, vector<Node>, Cmp> pq;
for (int i = 1; i <= n; ++i) {
long long v = query(i, 1);
pq.push({v, i, 1});
}
long long ans = 0;
for (long long cnt = 1; cnt <= t; ++cnt) {
Node cur = pq.top(); pq.pop();
if (cnt == t) {
ans = cur.val;
break;
}
int ni = cur.i, nj = cur.j + 1;
if (nj <= n) {
long long v = query(ni, nj);
pq.push({v, ni, nj});
}
}
done(ans);
} else {
// K-way merge from the end of each row (descending order)
struct Cmp {
bool operator()(const Node& a, const Node& b) const {
return a.val < b.val;
}
};
priority_queue<Node, vector<Node>, Cmp> pq;
for (int i = 1; i <= n; ++i) {
long long v = query(i, n);
pq.push({v, i, n});
}
long long ans = 0;
for (long long cnt = 1; cnt <= t; ++cnt) {
Node cur = pq.top(); pq.pop();
if (cnt == t) {
ans = cur.val;
break;
}
int ni = cur.i, nj = cur.j - 1;
if (nj >= 1) {
long long v = query(ni, nj);
pq.push({v, ni, nj});
}
}
done(ans);
}
return 0;
} |