#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int n;
int v_sum;
int find_v_sum() {
unordered_map<int, int> sum_freq;
for (int i = 0; i < min(n, 1000); i++) {
vector<int> res = ask(i);
sum_freq[res[0] + res[1]]++;
}
for (pii sf : sum_freq)
if (sf.second >= min(n / 2, 500)) return sf.first;
assert(true == false);
}
bool is_v(int res_sum) {
return res_sum == v_sum;
}
vector<int> append(vector<int> v1, vector<int> v2) {
v1.insert(v1.end(), v2.begin(), v2.end());
return v1;
}
vector<int> find_non_vs(int lo, int hi, int l, int r) {
// cout << "CALL " << lo << " " << hi << " " << l << " " << r << endl;
if (lo > hi) return {};
vector<int> ans, res;
int l_mid = (lo + hi) / 2, r_mid = (lo + hi) / 2;
while (r_mid <= hi) {
res = ask(r_mid);
if (is_v(res[0] + res[1])) break;
ans.push_back(r_mid);
r_mid++;
}
if (r_mid == hi + 1) return append(ans, find_non_vs(lo, l_mid - 1, l, r + r_mid - l_mid + 1));
int l_size = res[0] - l - (r_mid - l_mid);
int r_size = res[1] - r;
// cout << "DETAILS " << l_mid << " " << r_mid << " " << l_size << " " << r_size << endl;
assert(min(l_size, r_size) >= 0);
if (l_size == 0 && r_size == 0) return ans;
else if (l_size == 0) return append(ans, find_non_vs(r_mid + 1, hi, l + r_mid - l_mid, r));
else if (r_size == 0) return append(ans, find_non_vs(lo, l_mid - 1, l, r + r_mid - l_mid));
else {
vector<int> l_ans = find_non_vs(lo, l_mid - 1, l, r + r_size + r_mid - l_mid);
vector<int> r_ans = find_non_vs(r_mid + 1, hi, l + l_size + r_mid - l_mid, r);
return append(ans, append(l_ans, r_ans));
}
}
int find_best(int tmp_n) {
n = tmp_n;
v_sum = find_v_sum();
vector<int> non_vs = find_non_vs(0, n - 1, 0, 0);
for (int non_v : non_vs) {
vector<int> res = ask(non_v);
if (res[0] + res[1] == 0) return non_v;
}
assert(true == false);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
688 KB |
Output is correct |
| 2 |
Correct |
4 ms |
436 KB |
Output is correct |
| 3 |
Correct |
4 ms |
436 KB |
Output is correct |
| 4 |
Correct |
5 ms |
436 KB |
Output is correct |
| 5 |
Correct |
4 ms |
436 KB |
Output is correct |
| 6 |
Correct |
4 ms |
436 KB |
Output is correct |
| 7 |
Correct |
4 ms |
436 KB |
Output is correct |
| 8 |
Correct |
6 ms |
424 KB |
Output is correct |
| 9 |
Correct |
4 ms |
344 KB |
Output is correct |
| 10 |
Correct |
6 ms |
432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
432 KB |
Output is correct |
| 2 |
Correct |
4 ms |
436 KB |
Output is correct |
| 3 |
Correct |
4 ms |
436 KB |
Output is correct |
| 4 |
Correct |
4 ms |
440 KB |
Output is correct |
| 5 |
Correct |
7 ms |
436 KB |
Output is correct |
| 6 |
Correct |
5 ms |
436 KB |
Output is correct |
| 7 |
Correct |
5 ms |
344 KB |
Output is correct |
| 8 |
Correct |
5 ms |
436 KB |
Output is correct |
| 9 |
Correct |
5 ms |
340 KB |
Output is correct |
| 10 |
Correct |
5 ms |
436 KB |
Output is correct |
| 11 |
Correct |
6 ms |
608 KB |
Output is correct |
| 12 |
Correct |
6 ms |
432 KB |
Output is correct |
| 13 |
Correct |
5 ms |
440 KB |
Output is correct |
| 14 |
Correct |
7 ms |
692 KB |
Output is correct |
| 15 |
Partially correct |
25 ms |
688 KB |
Partially correct - number of queries: 5307 |
| 16 |
Partially correct |
34 ms |
688 KB |
Partially correct - number of queries: 5881 |
| 17 |
Partially correct |
23 ms |
692 KB |
Partially correct - number of queries: 5456 |
| 18 |
Partially correct |
24 ms |
444 KB |
Partially correct - number of queries: 5942 |
| 19 |
Partially correct |
19 ms |
612 KB |
Partially correct - number of queries: 5202 |
| 20 |
Correct |
16 ms |
440 KB |
Output is correct |
| 21 |
Partially correct |
30 ms |
440 KB |
Partially correct - number of queries: 5624 |
| 22 |
Correct |
22 ms |
436 KB |
Output is correct |
| 23 |
Correct |
4 ms |
436 KB |
Output is correct |
| 24 |
Correct |
6 ms |
608 KB |
Output is correct |
| 25 |
Partially correct |
22 ms |
696 KB |
Partially correct - number of queries: 5310 |
| 26 |
Partially correct |
23 ms |
684 KB |
Partially correct - number of queries: 5307 |
| 27 |
Correct |
4 ms |
436 KB |
Output is correct |
| 28 |
Partially correct |
25 ms |
1200 KB |
Partially correct - number of queries: 5404 |
| 29 |
Correct |
21 ms |
440 KB |
Output is correct |
| 30 |
Partially correct |
32 ms |
440 KB |
Partially correct - number of queries: 5899 |
| 31 |
Partially correct |
29 ms |
432 KB |
Partially correct - number of queries: 5437 |
| 32 |
Correct |
5 ms |
432 KB |
Output is correct |
| 33 |
Correct |
1 ms |
344 KB |
Output is correct |
| 34 |
Partially correct |
29 ms |
600 KB |
Partially correct - number of queries: 5632 |
| 35 |
Correct |
4 ms |
436 KB |
Output is correct |
| 36 |
Partially correct |
24 ms |
444 KB |
Partially correct - number of queries: 5505 |
| 37 |
Correct |
6 ms |
440 KB |
Output is correct |
| 38 |
Correct |
4 ms |
436 KB |
Output is correct |
| 39 |
Partially correct |
25 ms |
440 KB |
Partially correct - number of queries: 5596 |
| 40 |
Partially correct |
23 ms |
436 KB |
Partially correct - number of queries: 5280 |
| 41 |
Partially correct |
28 ms |
440 KB |
Partially correct - number of queries: 5705 |
| 42 |
Partially correct |
19 ms |
440 KB |
Partially correct - number of queries: 5705 |
| 43 |
Partially correct |
22 ms |
676 KB |
Partially correct - number of queries: 5597 |
| 44 |
Partially correct |
24 ms |
436 KB |
Partially correct - number of queries: 5662 |
| 45 |
Partially correct |
19 ms |
948 KB |
Partially correct - number of queries: 5185 |
| 46 |
Partially correct |
25 ms |
928 KB |
Partially correct - number of queries: 5467 |
| 47 |
Partially correct |
23 ms |
696 KB |
Partially correct - number of queries: 5353 |
| 48 |
Partially correct |
21 ms |
448 KB |
Partially correct - number of queries: 5786 |
| 49 |
Partially correct |
23 ms |
436 KB |
Partially correct - number of queries: 5473 |
| 50 |
Partially correct |
27 ms |
436 KB |
Partially correct - number of queries: 5936 |
| 51 |
Partially correct |
23 ms |
700 KB |
Partially correct - number of queries: 5639 |
| 52 |
Partially correct |
27 ms |
688 KB |
Partially correct - number of queries: 5472 |
| 53 |
Correct |
4 ms |
432 KB |
Output is correct |
| 54 |
Partially correct |
28 ms |
448 KB |
Partially correct - number of queries: 5647 |
| 55 |
Partially correct |
22 ms |
692 KB |
Partially correct - number of queries: 5466 |
| 56 |
Partially correct |
25 ms |
612 KB |
Partially correct - number of queries: 5947 |
| 57 |
Partially correct |
28 ms |
944 KB |
Partially correct - number of queries: 5771 |
| 58 |
Partially correct |
36 ms |
928 KB |
Partially correct - number of queries: 5781 |
| 59 |
Partially correct |
25 ms |
688 KB |
Partially correct - number of queries: 5709 |
| 60 |
Partially correct |
23 ms |
688 KB |
Partially correct - number of queries: 5675 |
| 61 |
Correct |
6 ms |
428 KB |
Output is correct |
| 62 |
Correct |
4 ms |
436 KB |
Output is correct |
| 63 |
Correct |
4 ms |
440 KB |
Output is correct |
| 64 |
Correct |
4 ms |
436 KB |
Output is correct |
| 65 |
Correct |
5 ms |
340 KB |
Output is correct |
| 66 |
Runtime error |
7 ms |
688 KB |
Execution killed with signal 6 |
| 67 |
Halted |
0 ms |
0 KB |
- |
