Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup
File size: 4,717 Bytes
1fd0050
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <bits/stdc++.h>
using namespace std;

static const int64_t MAXQ = 50000;

struct Node {
    long long val;
    int i, j;
    bool operator<(const Node& other) const {
        if (val != other.val) return val > other.val; // min-heap by default
        if (i != other.i) return i > other.i;
        return j > other.j;
    }
};
struct NodeMax {
    long long val;
    int i, j;
    bool operator<(const NodeMax& other) const {
        if (val != other.val) return val < other.val; // max-heap
        if (i != other.i) return i < other.i;
        return j < other.j;
    }
};

int n;
long long k;
long long queries_used = 0;

long long ask(int x, int y) {
    cout << "QUERY " << x << " " << y << "\n" << flush;
    long long v;
    if (!(cin >> v)) {
        // If interactor fails, return 0 to avoid UB
        exit(0);
    }
    queries_used++;
    return v;
}

long long solve_bfs_small_k(long long K) {
    vector<vector<char>> vis(n + 2, vector<char>(n + 2, 0));
    priority_queue<Node> pq; // min-heap via custom operator
    long long v = ask(1, 1);
    vis[1][1] = 1;
    pq.push({v, 1, 1});
    for (long long t = 1; t < K; ++t) {
        Node cur = pq.top(); pq.pop();
        int i = cur.i, j = cur.j;
        if (i + 1 <= n && !vis[i + 1][j]) {
            long long nv = ask(i + 1, j);
            vis[i + 1][j] = 1;
            pq.push({nv, i + 1, j});
        }
        if (j + 1 <= n && !vis[i][j + 1]) {
            long long nv = ask(i, j + 1);
            vis[i][j + 1] = 1;
            pq.push({nv, i, j + 1});
        }
    }
    return pq.top().val;
}

long long solve_bfs_small_m(long long M) {
    vector<vector<char>> vis(n + 2, vector<char>(n + 2, 0));
    priority_queue<NodeMax> pq; // max-heap
    long long v = ask(n, n);
    vis[n][n] = 1;
    pq.push({v, n, n});
    for (long long t = 1; t < M; ++t) {
        NodeMax cur = pq.top(); pq.pop();
        int i = cur.i, j = cur.j;
        if (i - 1 >= 1 && !vis[i - 1][j]) {
            long long nv = ask(i - 1, j);
            vis[i - 1][j] = 1;
            pq.push({nv, i - 1, j});
        }
        if (j - 1 >= 1 && !vis[i][j - 1]) {
            long long nv = ask(i, j - 1);
            vis[i][j - 1] = 1;
            pq.push({nv, i, j - 1});
        }
    }
    return pq.top().val;
}

long long solve_row_merge_k(long long K) {
    priority_queue<Node> pq; // min-heap
    for (int i = 1; i <= n; ++i) {
        long long v = ask(i, 1);
        pq.push({v, i, 1});
    }
    for (long long t = 1; t < K; ++t) {
        Node cur = pq.top(); pq.pop();
        int i = cur.i, j = cur.j;
        if (j + 1 <= n) {
            long long nv = ask(i, j + 1);
            pq.push({nv, i, j + 1});
        }
    }
    return pq.top().val;
}

long long solve_row_merge_m(long long M) {
    priority_queue<NodeMax> pq; // max-heap
    for (int i = 1; i <= n; ++i) {
        long long v = ask(i, n);
        pq.push({v, i, n});
    }
    for (long long t = 1; t < M; ++t) {
        NodeMax cur = pq.top(); pq.pop();
        int i = cur.i, j = cur.j;
        if (j - 1 >= 1) {
            long long nv = ask(i, j - 1);
            pq.push({nv, i, j - 1});
        }
    }
    return pq.top().val;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> k)) {
        return 0;
    }

    long long total = 1LL * n * n;
    long long m = total - k + 1;

    // Predict query counts for strategies
    auto safe_mul = [](long long a, long long b) -> long long {
        if (a == 0 || b == 0) return 0;
        if (a > (LLONG_MAX / b)) return LLONG_MAX / 2;
        return a * b;
    };

    long long pred_bfs_k = 1 + safe_mul(2, (k > 0 ? (k - 1) : 0));
    long long pred_bfs_m = 1 + safe_mul(2, (m > 0 ? (m - 1) : 0));
    long long pred_merge_k = n + (k > 0 ? (k - 1) : 0);
    long long pred_merge_m = n + (m > 0 ? (m - 1) : 0);

    // Choose the strategy with minimal predicted queries
    int strategy = 0;
    long long best_pred = LLONG_MAX;
    vector<pair<int, long long>> options = {
        {1, pred_bfs_k},   // BFS from min side
        {2, pred_bfs_m},   // BFS from max side
        {3, pred_merge_k}, // Row merge from min side
        {4, pred_merge_m}  // Row merge from max side
    };
    for (auto &op : options) {
        if (op.second < best_pred) {
            best_pred = op.second;
            strategy = op.first;
        }
    }

    long long ans = 0;
    if (strategy == 1) {
        ans = solve_bfs_small_k(k);
    } else if (strategy == 2) {
        ans = solve_bfs_small_m(m);
    } else if (strategy == 3) {
        ans = solve_row_merge_k(k);
    } else {
        ans = solve_row_merge_m(m);
    }

    cout << "DONE " << ans << "\n" << flush;
    return 0;
}