docker_space/frontier_cs_4/local_test16.cpp

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

struct TestCase {
    int n; long long k;
    vector<vector<long long>> A; 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_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_additive(int n, long long k) { return gen_matrix(n, k, [](int i, int j) -> long long { return i + j; }); }
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));
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) tc.A[i][j] = (long long)i * 1000000 + (long long)j * 1000 + (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;
}

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];
    }

    // Bounded staircase walk: count elements <= mid within jLo..jHi bounds
    // jLo[i] = last column known to be <= lo_threshold (0 if none)
    // jHi[i] = last column known to be <= hi_threshold
    // Returns count and new cutoff positions
    pair<long long, vector<int>> countLeq(long long mid, const vector<int>& jLo, const vector<int>& jHi) {
        vector<int> cutoff(n + 1, 0);
        long long cnt = 0;
        int j = jHi[1]; // start from upper bound of row 1
        if (j > n) j = n;
        for (int i = 1; i <= n; i++) {
            int lo = jLo[i];
            int hi = jHi[i];
            if (hi > n) hi = n;
            if (lo < 0) lo = 0;
            if (hi <= lo) {
                cutoff[i] = lo;
                cnt += lo;
                continue;
            }
            if (j > hi) j = hi;
            while (j > lo) {
                if (do_query(i, j) <= mid) {
                    cutoff[i] = j;
                    cnt += j;
                    goto next_row;
                }
                j--;
            }
            cutoff[i] = lo;
            cnt += lo;
            next_row:;
        }
        return {cnt, cutoff};
    }

    long long solve() {
        long long k = tc.k;
        long long NLL = (long long)n * n;
        if (n == 1) return do_query(1, 1);
        if (k == 1) return do_query(1, 1);
        if (k == NLL) return do_query(n, n);

        // For small/extreme k, use heap
        long long heap_k = min(k, NLL - k + 1);
        if (heap_k + n <= 24000) {
            if (k <= NLL - 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 = NLL - 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 approach with cached staircase walks
        vector<int> jLo(n + 1, 0), jHi(n + 1, n);
        long long cLo = 0, cHi = NLL;

        // Phase 1: Get initial value bounds
        // Query a strategic row to get candidate pivot values
        // Row ceil(k/n) is a good starting point
        int pivot_row = max(1, min(n, (int)((k + n - 1) / n)));

        // Query several strategic positions on this row for initial range
        long long min_val = do_query(1, 1);
        long long max_val = do_query(n, n);

        // Quick initial bound: use row pivot_row
        long long init_hi = do_query(pivot_row, n);
        auto [ch, cutH] = countLeq(init_hi, jLo, jHi);
        if (ch >= k) {
            jHi = cutH;
            cHi = ch;
            max_val = init_hi;
        }

        // Phase 2: Sample candidate pivot values for binary search
        // Query along the anti-diagonal and rows to get diverse values
        set<long long> cand_set;

        // Sample the diagonal
        for (int i = 1; i <= n; i += max(1, n / 50)) {
            cand_set.insert(do_query(i, i));
        }
        // Sample the pivot_row
        for (int j = 1; j <= n; j += max(1, n / 50)) {
            cand_set.insert(do_query(pivot_row, j));
        }
        // Sample a second row
        int row2 = max(1, min(n, pivot_row / 2));
        for (int j = 1; j <= n; j += max(1, n / 30)) {
            cand_set.insert(do_query(row2, j));
        }
        int row3 = min(n, pivot_row * 3 / 2);
        for (int j = 1; j <= n; j += max(1, n / 30)) {
            cand_set.insert(do_query(row3, j));
        }

        vector<long long> candidates(cand_set.begin(), cand_set.end());
        sort(candidates.begin(), candidates.end());

        // Phase 3: Binary search over candidate values
        int lo_idx = -1, hi_idx = (int)candidates.size();
        int max_walks = max(1, min(20, 40000 / (2 * n)));

        for (int w = 0; w < max_walks && hi_idx - lo_idx > 1; w++) {
            int mid_idx = lo_idx + (hi_idx - lo_idx) / 2;
            long long pivot = candidates[mid_idx];
            auto [cnt, cut] = countLeq(pivot, jLo, jHi);
            if (cnt >= k) {
                hi_idx = mid_idx;
                jHi = cut;
                cHi = cnt;
                max_val = pivot;
            } else {
                lo_idx = mid_idx;
                jLo = cut;
                cLo = cnt;
                min_val = pivot;
            }

            long long W = cHi - cLo;
            long long budget = 49500 - query_count;
            if (W <= budget) break;
        }

        // Phase 4: Numeric binary search if candidate values weren't fine-grained enough
        int extra_walks = max(1, min(15, (49000 - query_count) / (2 * n)));
        for (int w = 0; w < extra_walks; w++) {
            long long W = cHi - cLo;
            long long budget = 49500 - query_count;
            if (W <= budget) break;
            if (min_val >= max_val) break;

            long long mid_val = min_val + (max_val - min_val) / 2;
            if (mid_val <= min_val) mid_val = min_val + 1;
            if (mid_val >= max_val) break;

            auto [cnt, cut] = countLeq(mid_val, jLo, jHi);
            if (cnt >= k) {
                jHi = cut;
                cHi = cnt;
                max_val = mid_val;
            } else {
                jLo = cut;
                cLo = cnt;
                min_val = mid_val;
            }
        }

        // Phase 5: Enumerate
        long long W = cHi - cLo;
        long long rank = k - cLo;
        if (W <= 0 || rank <= 0) return min_val;

        vector<long long> cand;
        cand.reserve(min((long long)50000, W));
        for (int i = 1; i <= n; i++) {
            for (int j = jLo[i] + 1; j <= jHi[i]; j++) {
                cand.push_back(do_query(i, j));
            }
        }

        if (rank > (long long)cand.size()) return max_val;
        nth_element(cand.begin(), cand.begin() + (rank - 1), cand.end());
        return cand[rank - 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({"mult 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({"mult 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({"mult 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({"mult n=2000 k=100000", []{ return gen_multiplicative(2000, 100000); }});
    tests.push_back({"mult 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);
        int used = s.query_count;
        double score = !correct ? 0.0 : (used <= tc.n ? 1.0 : (used >= 50000 ? 0.0 : (50000.0 - used) / (50000.0 - tc.n)));
        printf("%-45s q=%6d %s score=%.4f\n", t.name.c_str(), used, correct ? "OK" : "WRONG", score);
    }
}