docker_space/frontier_cs_4/local_test2.cpp

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

// ---- Matrix generation ----
struct TestCase {
    int n;
    long long k;
    vector<vector<long long>> A; // 1-indexed
    long long answer;
};

mt19937_64 rng_gen(42);

TestCase gen_matrix(int n, long long k, function<long long(int,int)> valfn) {
    TestCase tc;
    tc.n = n; tc.k = k;
    tc.A.assign(n+1, vector<long long>(n+1, 0));
    vector<long long> all;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            tc.A[i][j] = valfn(i, j);
            all.push_back(tc.A[i][j]);
        }
    sort(all.begin(), all.end());
    tc.answer = all[k-1];
    return tc;
}

TestCase gen_additive(int n, long long k) {
    return gen_matrix(n, k, [](int i, int j) -> long long { return i + j; });
}
TestCase gen_multiplicative(int n, long long k) {
    return gen_matrix(n, k, [](int i, int j) -> long long { return (long long)i * j; });
}
TestCase gen_shifted(int n, long long k) {
    return gen_matrix(n, k, [n](int i, int j) -> long long { return (long long)(i + n) * (j + n); });
}
TestCase gen_random_sorted(int n, long long k) {
    TestCase tc;
    tc.n = n; tc.k = k;
    tc.A.assign(n+1, vector<long long>(n+1, 0));
    long long C = 1000000, D = 1000;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            tc.A[i][j] = (long long)i * C + (long long)j * D + (rng_gen() % 500);
    for (int i = 1; i <= n; i++)
        for (int j = 2; j <= n; j++)
            tc.A[i][j] = max(tc.A[i][j], tc.A[i][j-1]);
    for (int j = 1; j <= n; j++)
        for (int i = 2; i <= n; i++)
            tc.A[i][j] = max(tc.A[i][j], tc.A[i-1][j]);
    vector<long long> all;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            all.push_back(tc.A[i][j]);
    sort(all.begin(), all.end());
    tc.answer = all[k-1];
    return tc;
}

// ---- Solver (new value-based approach) ----
struct Solver {
    const TestCase& tc;
    int query_count;
    vector<long long> memo;
    int n;

    Solver(const TestCase& t) : tc(t), query_count(0), n(t.n) {
        memo.assign(2002 * 2002, -1);
    }

    long long do_query(int r, int c) {
        int key = r * 2001 + c;
        if (memo[key] != -1) return memo[key];
        query_count++;
        memo[key] = tc.A[r][c];
        return memo[key];
    }

    long long count_leq(long long x, vector<int>& pos) {
        pos.assign(n + 1, 0);
        long long cnt = 0;
        int j = n;
        for (int i = 1; i <= n; i++) {
            while (j >= 1 && do_query(i, j) > x) j--;
            pos[i] = j;
            cnt += j;
            if (j == 0) {
                for (int ii = i + 1; ii <= n; ii++) pos[ii] = 0;
                break;
            }
        }
        return cnt;
    }

    long long count_lt(long long x, vector<int>& pos) {
        pos.assign(n + 1, 0);
        long long cnt = 0;
        int j = n;
        for (int i = 1; i <= n; i++) {
            while (j >= 1 && do_query(i, j) >= x) j--;
            pos[i] = j;
            cnt += j;
            if (j == 0) {
                for (int ii = i + 1; ii <= n; ii++) pos[ii] = 0;
                break;
            }
        }
        return cnt;
    }

    long long solve() {
        long long k = tc.k;
        long long N2 = (long long)n * n;

        if (n == 1) return do_query(1, 1);
        if (k == 1) return do_query(1, 1);
        if (k == N2) return do_query(n, n);

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

        // Value-based narrowing
        mt19937_64 rng(12345);

        vector<int> posHigh(n + 1, n), posLow(n + 1, 0);
        long long cntHigh = N2, cntLow = 0;
        long long highTh, lowTh;

        int rBound = (int)min((long long)n, (k + n - 1) / n);
        highTh = do_query(rBound, n);
        cntHigh = count_leq(highTh, posHigh);
        if (cntHigh < k) {
            highTh = do_query(n, n);
            cntHigh = count_leq(highTh, posHigh);
        }
        lowTh = do_query(1, 1) - 1;

        const int SAMPLES = 15;

        for (int iter = 0; iter < 200; iter++) {
            if (cntHigh < k) {
                highTh = do_query(n, n);
                cntHigh = count_leq(highTh, posHigh);
                if (cntHigh < k) break;
            }

            long long candTotal = cntHigh - cntLow;
            if (candTotal <= 0) return highTh; // shouldn't happen with correct answer

            long long needSmall = k - cntLow;
            long long needLarge = cntHigh - k + 1;

            vector<long long> pref(n + 1, 0);
            int nonempty = 0;
            for (int i = 1; i <= n; i++) {
                int len = posHigh[i] - posLow[i];
                if (len > 0) nonempty++;
                pref[i] = pref[i - 1] + max(0, len);
            }
            candTotal = pref[n];
            if (candTotal <= 0) return highTh;

            long long budget = 49500 - query_count;
            long long enumCost = min(needSmall, needLarge) + nonempty + 10;
            if (enumCost <= budget) {
                if (needSmall <= needLarge) {
                    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<>> pq;
                    for (int i = 1; i <= n; i++) {
                        int L = posLow[i] + 1, R = posHigh[i];
                        if (L >= 1 && L <= n && L <= R) pq.emplace(do_query(i, L), i, L);
                    }
                    long long result = 0;
                    for (long long t = 0; t < needSmall; t++) {
                        auto [v, r, c] = pq.top(); pq.pop();
                        result = v;
                        if (c + 1 <= posHigh[r]) pq.emplace(do_query(r, c + 1), r, c + 1);
                    }
                    return result;
                } else {
                    priority_queue<tuple<long long, int, int>> pq;
                    for (int i = 1; i <= n; i++) {
                        int L = posLow[i] + 1, R = posHigh[i];
                        if (R >= 1 && R <= n && L <= R) pq.emplace(do_query(i, R), i, R);
                    }
                    long long result = 0;
                    for (long long t = 0; t < needLarge; t++) {
                        auto [v, r, c] = pq.top(); pq.pop();
                        result = v;
                        if (c - 1 >= posLow[r] + 1) pq.emplace(do_query(r, c - 1), r, c - 1);
                    }
                    return result;
                }
            }

            if (budget < 2 * n + SAMPLES + 200) {
                return highTh; // last resort
            }

            // Sample pivots
            vector<long long> samp;
            samp.reserve(SAMPLES);
            for (int s = 0; s < SAMPLES; s++) {
                long long pick = 1 + rng() % candTotal;
                int row = (int)(lower_bound(pref.begin() + 1, pref.end(), pick) - pref.begin());
                if (row < 1 || row > n) continue;
                int len = posHigh[row] - posLow[row];
                if (len <= 0) continue;
                int col = posLow[row] + 1 + rng() % len;
                col = max(1, min(n, col));
                samp.push_back(do_query(row, col));
            }
            if (samp.empty()) return highTh;

            sort(samp.begin(), samp.end());
            double q = (double)needSmall / (double)candTotal;
            int idx = (int)(q * (double)(samp.size() - 1));
            idx = max(0, min((int)samp.size() - 1, idx));
            long long pivot = samp[idx];

            vector<int> posPivot;
            long long cntPivot = count_leq(pivot, posPivot);

            if (cntPivot >= k) {
                if (pivot == highTh && cntPivot == cntHigh) {
                    vector<int> posLess;
                    long long cntLess = count_lt(pivot, posLess);
                    if (cntLess < k) return pivot;
                    highTh = pivot - 1;
                    posHigh = posLess;
                    cntHigh = cntLess;
                } else {
                    highTh = pivot;
                    posHigh = posPivot;
                    cntHigh = cntPivot;
                }
            } else {
                lowTh = pivot;
                posLow = posPivot;
                cntLow = cntPivot;
            }
        }
        return -1;
    }
};

int main() {
    struct TestDef {
        string name;
        function<TestCase()> gen;
    };

    vector<TestDef> tests;
    tests.push_back({"additive n=100 k=5000", []{ return gen_additive(100, 5000); }});
    tests.push_back({"multiplicative n=100 k=5000", []{ return gen_multiplicative(100, 5000); }});
    tests.push_back({"additive n=500 k=125000", []{ return gen_additive(500, 125000); }});
    tests.push_back({"multiplicative n=500 k=125000", []{ return gen_multiplicative(500, 125000); }});
    tests.push_back({"random n=500 k=125000", []{ return gen_random_sorted(500, 125000); }});
    tests.push_back({"additive n=2000 k=2000000", []{ return gen_additive(2000, 2000000); }});
    tests.push_back({"multiplicative n=2000 k=2000000", []{ return gen_multiplicative(2000, 2000000); }});
    tests.push_back({"shifted n=2000 k=2000000", []{ return gen_shifted(2000, 2000000); }});
    tests.push_back({"random n=2000 k=2000000", []{ return gen_random_sorted(2000, 2000000); }});
    tests.push_back({"multiplicative n=2000 k=1", []{ return gen_multiplicative(2000, 1); }});
    tests.push_back({"multiplicative n=2000 k=4000000", []{ return gen_multiplicative(2000, 4000000); }});
    tests.push_back({"multiplicative n=2000 k=100000", []{ return gen_multiplicative(2000, 100000); }});
    tests.push_back({"multiplicative n=2000 k=3900000", []{ return gen_multiplicative(2000, 3900000); }});

    for (auto& t : tests) {
        auto tc = t.gen();
        Solver s(tc);
        long long result = s.solve();
        bool correct = (result == tc.answer);
        double score;
        int n = tc.n;
        int used = s.query_count;
        if (!correct) score = 0.0;
        else if (used <= n) score = 1.0;
        else if (used >= 50000) score = 0.0;
        else score = (50000.0 - used) / (50000.0 - n);

        printf("%-45s n=%4d k=%8lld queries=%6d correct=%s score=%.4f\n",
               t.name.c_str(), tc.n, tc.k, used, correct ? "YES" : "NO", score);
    }
    return 0;
}