Add files using upload-large-folder tool

1fd0050 verified 6 months ago

11.1 kB

#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));
    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;
}

// Improved solver: use binary search within each row instead of staircase walk
// For pivot partitioning, binary search in each active row for the rightmost col <= pivot
// This is O(n * log(width)) per iteration but caches well
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 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);

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

        // Binary-search-in-row approach: for each row, find rightmost col <= pivot via binary search
        // Then use staircase constraint to tighten bounds
        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) 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());
            }

            // Use median-of-samples pivot selection with position-weighted sampling
            // Build prefix sum of widths for uniform position-based sampling
            vector<long long> pref(na + 1, 0);
            for (int idx = 0; idx < na; idx++) {
                int i = active[idx];
                pref[idx + 1] = pref[idx] + (R[i] - L[i] + 1);
            }

            mt19937_64 rng(iter * 1234567 + 42);
            int num_samples = min(15, (int)(budget / 2)); // don't waste too many
            num_samples = min(num_samples, (int)min((long long)na * 3, total_cand));
            num_samples = max(num_samples, 5);

            vector<long long> samp;
            for (int s = 0; s < num_samples; s++) {
                long long pick = 1 + rng() % total_cand;
                int idx = (int)(lower_bound(pref.begin() + 1, pref.end(), pick) - pref.begin()) - 1;
                idx = max(0, min(na - 1, idx));
                int i = active[idx];
                int width = R[i] - L[i] + 1;
                int col = L[i] + rng() % width;
                samp.push_back(do_query(i, col));
            }
            sort(samp.begin(), samp.end());

            // Pick pivot at appropriate quantile
            double q = (double)(k_rem - 0.5) / total_cand;
            int pidx = (int)(q * (double)(samp.size() - 1));
            pidx = max(0, min((int)samp.size() - 1, pidx));
            long long pivot = samp[pidx];

            // Staircase walk to partition
            // Use binary search in each row, constrained by staircase monotonicity
            vector<int> p_le(n + 1, 0); // rightmost col in row i where val <= pivot

            // Top-to-bottom staircase: p_le[i] >= p_le[i+1] won't hold.
            // Actually for sorted matrix: if a[i][j] <= pivot, then a[i-1][j] <= pivot (col monotonicity)
            // So p_le[i] >= p_le[i+1] (higher rows have more elements <= pivot)
            // Walk top-to-bottom, p_le starts at R[1] and can only decrease

            {
                int upper = n; // upper bound for binary search
                for (int idx = 0; idx < na; idx++) {
                    int i = active[idx];
                    int lo = L[i] - 1, hi = min(R[i], upper);
                    // Binary search: find rightmost col in [L[i], hi] where a[i][col] <= pivot
                    // lo = L[i]-1 means "no element <= pivot"
                    while (lo < hi) {
                        int mid = lo + (hi - lo + 1) / 2;
                        if (do_query(i, mid) <= pivot) lo = mid;
                        else hi = mid - 1;
                    }
                    p_le[i] = lo;
                    upper = lo; // staircase: next row can't have more
                    if (upper < 1) {
                        // Remaining rows have p_le = 0
                        for (int idx2 = idx + 1; idx2 < na; idx2++)
                            p_le[active[idx2]] = 0;
                        break;
                    }
                }
            }

            long long cle = 0;
            for (int i : active) {
                if (p_le[i] >= L[i]) cle += p_le[i] - L[i] + 1;
            }

            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({"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 used = s.query_count;
        if (!correct) score = 0.0;
        else if (used <= tc.n) score = 1.0;
        else if (used >= 50000) score = 0.0;
        else score = (50000.0 - used) / (50000.0 - tc.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;
}

	#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));
	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;
	}

	// Improved solver: use binary search within each row instead of staircase walk
	// For pivot partitioning, binary search in each active row for the rightmost col <= pivot
	// This is O(n * log(width)) per iteration but caches well
	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 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);

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

	// Binary-search-in-row approach: for each row, find rightmost col <= pivot via binary search
	// Then use staircase constraint to tighten bounds
	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) 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());
	}

	// Use median-of-samples pivot selection with position-weighted sampling
	// Build prefix sum of widths for uniform position-based sampling
	vector<long long> pref(na + 1, 0);
	for (int idx = 0; idx < na; idx++) {
	int i = active[idx];
	pref[idx + 1] = pref[idx] + (R[i] - L[i] + 1);
	}

	mt19937_64 rng(iter * 1234567 + 42);
	int num_samples = min(15, (int)(budget / 2)); // don't waste too many
	num_samples = min(num_samples, (int)min((long long)na * 3, total_cand));
	num_samples = max(num_samples, 5);

	vector<long long> samp;
	for (int s = 0; s < num_samples; s++) {
	long long pick = 1 + rng() % total_cand;
	int idx = (int)(lower_bound(pref.begin() + 1, pref.end(), pick) - pref.begin()) - 1;
	idx = max(0, min(na - 1, idx));
	int i = active[idx];
	int width = R[i] - L[i] + 1;
	int col = L[i] + rng() % width;
	samp.push_back(do_query(i, col));
	}
	sort(samp.begin(), samp.end());

	// Pick pivot at appropriate quantile
	double q = (double)(k_rem - 0.5) / total_cand;
	int pidx = (int)(q * (double)(samp.size() - 1));
	pidx = max(0, min((int)samp.size() - 1, pidx));
	long long pivot = samp[pidx];

	// Staircase walk to partition
	// Use binary search in each row, constrained by staircase monotonicity
	vector<int> p_le(n + 1, 0); // rightmost col in row i where val <= pivot

	// Top-to-bottom staircase: p_le[i] >= p_le[i+1] won't hold.
	// Actually for sorted matrix: if a[i][j] <= pivot, then a[i-1][j] <= pivot (col monotonicity)
	// So p_le[i] >= p_le[i+1] (higher rows have more elements <= pivot)
	// Walk top-to-bottom, p_le starts at R[1] and can only decrease

	{
	int upper = n; // upper bound for binary search
	for (int idx = 0; idx < na; idx++) {
	int i = active[idx];
	int lo = L[i] - 1, hi = min(R[i], upper);
	// Binary search: find rightmost col in [L[i], hi] where a[i][col] <= pivot
	// lo = L[i]-1 means "no element <= pivot"
	while (lo < hi) {
	int mid = lo + (hi - lo + 1) / 2;
	if (do_query(i, mid) <= pivot) lo = mid;
	else hi = mid - 1;
	}
	p_le[i] = lo;
	upper = lo; // staircase: next row can't have more
	if (upper < 1) {
	// Remaining rows have p_le = 0
	for (int idx2 = idx + 1; idx2 < na; idx2++)
	p_le[active[idx2]] = 0;
	break;
	}
	}
	}

	long long cle = 0;
	for (int i : active) {
	if (p_le[i] >= L[i]) cle += p_le[i] - L[i] + 1;
	}

	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({"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 used = s.query_count;
	if (!correct) score = 0.0;
	else if (used <= tc.n) score = 1.0;
	else if (used >= 50000) score = 0.0;
	else score = (50000.0 - used) / (50000.0 - tc.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;
	}