docker_space/frontier_cs_4/local_test18.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];
    }

    // Returns (cle, p_le) where p_le[i] = rightmost col in row i with value <= pivot
    pair<long long, vector<int>> walk(long long pivot, const vector<int>& active, const vector<int>& L, const vector<int>& R) {
        int na = active.size();
        vector<int> p_le(n + 1, 0);
        int j = 0;
        for (int idx = na - 1; idx >= 0; idx--) {
            int i = active[idx];
            j = max(j, L[i]);
            while (j <= R[i] && do_query(i, j) <= pivot) j++;
            p_le[i] = j - 1;
        }
        long long cle = 0;
        for (int i : active) {
            int rl = min(p_le[i], R[i]);
            if (rl >= L[i]) cle += rl - L[i] + 1;
        }
        return {cle, p_le};
    }

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

        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;
                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); }
                }
                return result;
            } else {
                long long kk = N2 - 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); }
                }
                return result;
            }
        }

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

        // Track value bounds for correction
        long long best_lo_val = LLONG_MIN; // largest value v such that count_leq(v) < k_rem
        long long best_hi_val = LLONG_MAX; // smallest value v such that count_leq(v) >= k_rem
        long long best_lo_cnt = 0, best_hi_cnt = N2;

        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) return do_query(i, L[i]); break; }

            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);
                }
                return 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);
                }
                return get<0>(pq.top());
            }

            // Pivot selection (original method)
            double target_frac = (double)(k_rem - 0.5) / total_cand;
            vector<long long> pvals;
            int sample_n = max(1, min(na, (int)ceil(sqrt((double)na) * 4)));
            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);
                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];

            // If we have value bounds, try to interpolate a better pivot
            if (best_lo_val != LLONG_MIN && best_hi_val != LLONG_MAX && best_hi_val > best_lo_val) {
                // Interpolate: target count within current L/R is k_rem
                // The total count including eliminated elements:
                // count_leq(best_lo_val) < k (globally), count_leq(best_hi_val) >= k (globally)
                // Within current L/R bounds, elements are between best_lo_val and best_hi_val
                // Use linear interpolation
                double frac = (double)(k_rem) / total_cand;
                long long interp_val = best_lo_val + (long long)(frac * (best_hi_val - best_lo_val));
                // Use interpolated value as pivot if it seems reasonable
                // (it must be between min and max sampled values)
                if (interp_val > pvals.front() && interp_val < pvals.back()) {
                    // Average with the sampled median
                    pivot = (pivot + interp_val) / 2;
                } else if (interp_val >= pvals.front() && interp_val <= pvals.back()) {
                    pivot = interp_val;
                }
            }

            // Staircase walk
            auto [cle, p_le] = walk(pivot, active, L, R);

            // Update value bounds
            if (cle >= k_rem) {
                if (pivot < best_hi_val) { best_hi_val = pivot; best_hi_cnt = cle; }
            } else {
                if (pivot > best_lo_val) { best_lo_val = pivot; best_lo_cnt = cle; }
            }

            // Check split quality
            double split_ratio = (double)min(cle, total_cand - cle) / total_cand;

            // If split is poor (<15%), try a corrected pivot using value bounds
            if (split_ratio < 0.15 && best_lo_val != LLONG_MIN && best_hi_val != LLONG_MAX && budget > 2 * n + 500) {
                long long corrected_pivot = best_lo_val + (best_hi_val - best_lo_val) / 2;
                if (corrected_pivot > best_lo_val && corrected_pivot < best_hi_val && corrected_pivot != pivot) {
                    auto [cle2, p_le2] = walk(corrected_pivot, active, L, R);
                    double split2 = (double)min(cle2, total_cand - cle2) / total_cand;

                    // Update value bounds
                    if (cle2 >= k_rem) {
                        if (corrected_pivot < best_hi_val) { best_hi_val = corrected_pivot; best_hi_cnt = cle2; }
                    } else {
                        if (corrected_pivot > best_lo_val) { best_lo_val = corrected_pivot; best_lo_cnt = cle2; }
                    }

                    // Use whichever gives better split
                    if (split2 > split_ratio) {
                        cle = cle2;
                        p_le = p_le2;
                    }
                }
            }

            // Apply partition
            if (cle >= k_rem) {
                for (int i : active) R[i] = min(R[i], p_le[i]);
            } else {
                k_rem -= cle;
                for (int i : active) L[i] = max(L[i], p_le[i] + 1);
            }
        }
        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({"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);
    }
}