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