Add files using upload-large-folder tool

1fd0050 verified 6 months ago

5.45 kB

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

int n;
long long k;

vector<long long> memo;
int query_count = 0;

long long do_query(int r, int c) {
    int key = r * 2001 + c;
    if (memo[key] != -1) return memo[key];
    cout << "QUERY " << r << " " << c << "\n";
    cout.flush();
    long long v;
    cin >> v;
    memo[key] = v;
    query_count++;
    return v;
}

void done(long long ans) {
    cout << "DONE " << ans << "\n";
    cout.flush();
    exit(0);
}

void solve() {
    long long total = (long long)n * n;

    if (n == 1) { done(do_query(1, 1)); return; }

    // Heap for extreme k
    long long heap_k = min(k, total - k + 1);
    if (heap_k + n <= 24000) {
        if (k <= total - 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); }
            }
            done(result);
        } else {
            long long kk = total - 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); }
            }
            done(result);
        }
    }

    // Single-walk quickselect: only do <= walk, no < walk
    // This saves one walk per iteration at the cost of not detecting exact pivot match
    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) done(do_query(i, L[i]));
            break;
        }

        // Heap fallback
        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);
            }
            done(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);
            }
            done(get<0>(pq.top()));
        }

        // Pivot selection
        vector<long long> pvals;
        double target_frac = (double)(k_rem - 0.5) / total_cand;
        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];

        // Single staircase walk: bottom-to-top, left-to-right (reversed)
        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;
        }

        if (cle >= k_rem) {
            // Answer is <= pivot. Narrow right.
            for (int i : active) R[i] = min(R[i], p_le[i]);
        } else {
            // Answer is > pivot. Narrow left.
            k_rem -= cle;
            for (int i : active) L[i] = max(L[i], p_le[i] + 1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    memo.assign(2002 * 2002, -1);
    solve();
    return 0;
}

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

	int n;
	long long k;

	vector<long long> memo;
	int query_count = 0;

	long long do_query(int r, int c) {
	int key = r * 2001 + c;
	if (memo[key] != -1) return memo[key];
	cout << "QUERY " << r << " " << c << "\n";
	cout.flush();
	long long v;
	cin >> v;
	memo[key] = v;
	query_count++;
	return v;
	}

	void done(long long ans) {
	cout << "DONE " << ans << "\n";
	cout.flush();
	exit(0);
	}

	void solve() {
	long long total = (long long)n * n;

	if (n == 1) { done(do_query(1, 1)); return; }

	// Heap for extreme k
	long long heap_k = min(k, total - k + 1);
	if (heap_k + n <= 24000) {
	if (k <= total - 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); }
	}
	done(result);
	} else {
	long long kk = total - 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); }
	}
	done(result);
	}
	}

	// Single-walk quickselect: only do <= walk, no < walk
	// This saves one walk per iteration at the cost of not detecting exact pivot match
	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) done(do_query(i, L[i]));
	break;
	}

	// Heap fallback
	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);
	}
	done(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);
	}
	done(get<0>(pq.top()));
	}

	// Pivot selection
	vector<long long> pvals;
	double target_frac = (double)(k_rem - 0.5) / total_cand;
	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];

	// Single staircase walk: bottom-to-top, left-to-right (reversed)
	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;
	}

	if (cle >= k_rem) {
	// Answer is <= pivot. Narrow right.
	for (int i : active) R[i] = min(R[i], p_le[i]);
	} else {
	// Answer is > pivot. Narrow left.
	k_rem -= cle;
	for (int i : active) L[i] = max(L[i], p_le[i] + 1);
	}
	}
	}

	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	memo.assign(2002 * 2002, -1);
	solve();
	return 0;
	}