docker_space/frontier_cs_4/solution_backup.cpp

#include <bits/stdc++.h>
using namespace std;

int n;
long long k;

vector<long long> memo;
int query_count = 0;

long long do_query(int r, int c) {
    int key = r * 2001 + c;
    if (memo[key] != -1) return memo[key];
    cout << "QUERY " << r << " " << c << "\n";
    cout.flush();
    long long v;
    cin >> v;
    memo[key] = v;
    query_count++;
    return v;
}

void done(long long ans) {
    cout << "DONE " << ans << "\n";
    cout.flush();
    exit(0);
}

void solve() {
    long long total = (long long)n * n;

    if (n == 1) { done(do_query(1, 1)); return; }

    // Heap for extreme k
    long long heap_k = min(k, total - k + 1);
    if (heap_k + n <= 24000) {
        if (k <= total - k + 1) {
            priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<>> pq;
            vector<vector<bool>> vis(n + 1, vector<bool>(n + 1, false));
            pq.emplace(do_query(1, 1), 1, 1);
            vis[1][1] = true;
            long long result = -1;
            for (long long i = 0; i < k; i++) {
                auto [v, r, c] = pq.top(); pq.pop();
                result = v;
                if (r + 1 <= n && !vis[r + 1][c]) { vis[r + 1][c] = true; pq.emplace(do_query(r + 1, c), r + 1, c); }
                if (c + 1 <= n && !vis[r][c + 1]) { vis[r][c + 1] = true; pq.emplace(do_query(r, c + 1), r, c + 1); }
            }
            done(result);
        } else {
            long long kk = total - k + 1;
            priority_queue<tuple<long long, int, int>> pq;
            vector<vector<bool>> vis(n + 1, vector<bool>(n + 1, false));
            pq.emplace(do_query(n, n), n, n);
            vis[n][n] = true;
            long long result = -1;
            for (long long i = 0; i < kk; i++) {
                auto [v, r, c] = pq.top(); pq.pop();
                result = v;
                if (r - 1 >= 1 && !vis[r - 1][c]) { vis[r - 1][c] = true; pq.emplace(do_query(r - 1, c), r - 1, c); }
                if (c - 1 >= 1 && !vis[r][c - 1]) { vis[r][c - 1] = true; pq.emplace(do_query(r, c - 1), r, c - 1); }
            }
            done(result);
        }
    }

    // Quickselect
    vector<int> L(n + 1, 1), R(n + 1, n);
    long long k_rem = k;

    for (int iter = 0; iter < 100; iter++) {
        vector<int> active;
        long long total_cand = 0;
        for (int i = 1; i <= n; i++) {
            if (L[i] <= R[i]) {
                active.push_back(i);
                total_cand += R[i] - L[i] + 1;
            }
        }
        int na = active.size();
        if (total_cand == 0) break;
        if (total_cand == 1) {
            for (int i : active) done(do_query(i, L[i]));
            break;
        }

        // Heap fallback
        long long budget = 49500 - query_count;
        if (k_rem + na <= budget) {
            priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<>> pq;
            for (int i : active) pq.emplace(do_query(i, L[i]), i, L[i]);
            for (long long t = 1; t < k_rem; t++) {
                auto [v, r, c] = pq.top(); pq.pop();
                if (c + 1 <= R[r]) pq.emplace(do_query(r, c + 1), r, c + 1);
            }
            done(get<0>(pq.top()));
        }
        long long rev_k = total_cand - k_rem + 1;
        if (rev_k + na <= budget) {
            priority_queue<tuple<long long, int, int>> pq;
            for (int i : active) pq.emplace(do_query(i, R[i]), i, R[i]);
            for (long long t = 1; t < rev_k; t++) {
                auto [v, r, c] = pq.top(); pq.pop();
                if (c - 1 >= L[r]) pq.emplace(do_query(r, c - 1), r, c - 1);
            }
            done(get<0>(pq.top()));
        }

        // Pick pivot: sample sqrt(na) rows, query at target fraction
        vector<long long> pvals;
        double target_frac = (double)(k_rem - 0.5) / total_cand;
        int sample_n = max(1, min(na, (int)ceil(sqrt((double)na) * 2)));
        int step = max(1, na / sample_n);
        for (int idx = 0; idx < na; idx += step) {
            int i = active[idx];
            int width = R[i] - L[i] + 1;
            int col = L[i] + (int)(target_frac * (width - 1));
            col = max(L[i], min(R[i], col));
            pvals.push_back(do_query(i, col));
        }
        sort(pvals.begin(), pvals.end());
        long long pivot = pvals[pvals.size() / 2];

        // Staircase walks
        vector<int> p_le(n + 1, 0), p_lt(n + 1, 0);
        {
            int j = n;
            for (int i : active) {
                j = min(j, R[i]);
                while (j >= L[i] && do_query(i, j) > pivot) j--;
                p_le[i] = j;
            }
        }
        {
            int j = n;
            for (int i : active) {
                j = min(j, R[i]);
                while (j >= L[i] && do_query(i, j) >= pivot) j--;
                p_lt[i] = j;
            }
        }

        long long cle = 0, clt = 0;
        for (int i : active) {
            int rl = min(p_le[i], R[i]);
            if (rl >= L[i]) cle += rl - L[i] + 1;
            int rt = min(p_lt[i], R[i]);
            if (rt >= L[i]) clt += rt - L[i] + 1;
        }

        if (k_rem <= clt) {
            for (int i : active) R[i] = min(R[i], p_lt[i]);
        } else if (k_rem <= cle) {
            done(pivot);
        } else {
            k_rem -= cle;
            for (int i : active) L[i] = max(L[i], p_le[i] + 1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    memo.assign(2002 * 2002, -1);
    solve();
    return 0;
}