Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup
File size: 3,127 Bytes
14c9c2b
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <functional>
#include <tuple>

using namespace std;

long long n;
long long k;

map<pair<int, int>, long long> memo;

long long do_query(int r, int c) {
    if (memo.count({r, c})) {
        return memo[{r, c}];
    }
    cout << "QUERY " << r << " " << c << endl;
    long long v;
    cin >> v;
    return memo[{r, c}] = v;
}

void done(long long ans) {
    cout << "DONE " << ans << endl;
}

void solve_dijkstra_min() {
    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq;
    vector<vector<bool>> visited(n + 1, vector<bool>(n + 1, false));

    long long val = do_query(1, 1);
    pq.emplace(val, 1, 1);
    visited[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 && !visited[r + 1][c]) {
            long long next_val = do_query(r + 1, c);
            pq.emplace(next_val, r + 1, c);
            visited[r + 1][c] = true;
        }
        if (c + 1 <= n && !visited[r][c + 1]) {
            long long next_val = do_query(r, c + 1);
            pq.emplace(next_val, r, c + 1);
            visited[r][c + 1] = true;
        }
    }
    done(result);
}

void solve_dijkstra_max() {
    long long k_rev = n * n - k + 1;
    priority_queue<tuple<long long, int, int>> pq;
    vector<vector<bool>> visited(n + 1, vector<bool>(n + 1, false));

    long long val = do_query(n, n);
    pq.emplace(val, n, n);
    visited[n][n] = true;

    long long result = -1;
    for (long long i = 0; i < k_rev; ++i) {
        auto [v, r, c] = pq.top();
        pq.pop();
        result = v;

        if (r - 1 >= 1 && !visited[r - 1][c]) {
            long long next_val = do_query(r - 1, c);
            pq.emplace(next_val, r - 1, c);
            visited[r - 1][c] = true;
        }
        if (c - 1 >= 1 && !visited[r][c - 1]) {
            long long next_val = do_query(r, c - 1);
            pq.emplace(next_val, r, c - 1);
            visited[r][c - 1] = true;
        }
    }
    done(result);
}

long long count_le(long long val) {
    long long count = 0;
    int c = n;
    for (int r = 1; r <= n; ++r) {
        while (c >= 1 && do_query(r, c) > val) {
            c--;
        }
        count += c;
    }
    return count;
}

void solve_binary_search() {
    long long low = do_query(1, 1);
    long long high = do_query(n, n);
    long long ans = high;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (count_le(mid) >= k) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    done(ans);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;

    long long dijkstra_k_threshold = 24500;
    if (k <= dijkstra_k_threshold) {
        solve_dijkstra_min();
    } else if (n * n - k + 1 <= dijkstra_k_threshold) {
        solve_dijkstra_max();
    } else {
        solve_binary_search();
    }

    return 0;
}