#include "library.h"
#include <bits/stdc++.h>
#define long long long
using namespace std;
const int N = 1e3+5;
const int M = 98765431;
long mpow[N];
map<long, int> mp;
int ask(vector<int> &v) {
if(!accumulate(v.begin(), v.end(), 0)) return 0;
long hsh = 0;
for(int i = 0; i < v.size(); i++) if(v[i]) hsh += mpow[i];
if(!mp.count(hsh)) return mp[hsh] = Query(v);
else return mp[hsh];
}
int n;
vector<int> vec, ans;
void Solve(int _n) {
mpow[0] = 1, n = _n;
for(int i = 1; i < N; i++) mpow[i] = mpow[i-1] * M;
vec = vector<int>(n);
int l = 0, r = n-1;
while(l < r) {
int mid = (l + r) >> 1;
vector<int> now = vec;
for(int i = l; i <= mid; i++) now[i] = 1;
int q1 = ask(now);
for(int i = 0; i < n; i++) now[i] ^= 1;
int q2 = ask(now);
if(q1 >= q2) r = mid;
else l = mid + 1;
}
ans.emplace_back(r + 1), vec[r] = 1;
for(int i = 1; i < n; i++) {
int l = 0, r = n-1;
while(l < r) {
int mid = (l + r) >> 1;
vector<int> now = vec;
for(int i = l; i <= mid; i++) now[i] = 1;
int q1 = ask(now);
now[ans.back() - 1] = 0;
int q2 = ask(now);
if(i == 1) {
if(q1 == q2) r = mid;
else l = mid + 1;
} else {
if(q1 < q2) r = mid;
else l = mid + 1;
}
}
ans.emplace_back(r + 1), vec[r] = 1;
}
Answer(ans);
}
Compilation message
library.cpp: In function 'int ask(std::vector<int>&)':
library.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v.size(); i++) if(v[i]) hsh += mpow[i];
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
504 KB |
# of queries: 2121 |
| 2 |
Correct |
48 ms |
504 KB |
# of queries: 2160 |
| 3 |
Correct |
42 ms |
504 KB |
# of queries: 2278 |
| 4 |
Correct |
44 ms |
504 KB |
# of queries: 2205 |
| 5 |
Correct |
43 ms |
376 KB |
# of queries: 2277 |
| 6 |
Correct |
46 ms |
376 KB |
# of queries: 2244 |
| 7 |
Correct |
40 ms |
428 KB |
# of queries: 2221 |
| 8 |
Correct |
40 ms |
528 KB |
# of queries: 2115 |
| 9 |
Correct |
48 ms |
376 KB |
# of queries: 2253 |
| 10 |
Correct |
23 ms |
376 KB |
# of queries: 1264 |
| 11 |
Correct |
4 ms |
248 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
248 KB |
# of queries: 2 |
| 13 |
Correct |
5 ms |
248 KB |
# of queries: 5 |
| 14 |
Correct |
5 ms |
376 KB |
# of queries: 8 |
| 15 |
Correct |
6 ms |
376 KB |
# of queries: 69 |
| 16 |
Correct |
7 ms |
376 KB |
# of queries: 165 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
504 KB |
# of queries: 2121 |
| 2 |
Correct |
48 ms |
504 KB |
# of queries: 2160 |
| 3 |
Correct |
42 ms |
504 KB |
# of queries: 2278 |
| 4 |
Correct |
44 ms |
504 KB |
# of queries: 2205 |
| 5 |
Correct |
43 ms |
376 KB |
# of queries: 2277 |
| 6 |
Correct |
46 ms |
376 KB |
# of queries: 2244 |
| 7 |
Correct |
40 ms |
428 KB |
# of queries: 2221 |
| 8 |
Correct |
40 ms |
528 KB |
# of queries: 2115 |
| 9 |
Correct |
48 ms |
376 KB |
# of queries: 2253 |
| 10 |
Correct |
23 ms |
376 KB |
# of queries: 1264 |
| 11 |
Correct |
4 ms |
248 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
248 KB |
# of queries: 2 |
| 13 |
Correct |
5 ms |
248 KB |
# of queries: 5 |
| 14 |
Correct |
5 ms |
376 KB |
# of queries: 8 |
| 15 |
Correct |
6 ms |
376 KB |
# of queries: 69 |
| 16 |
Correct |
7 ms |
376 KB |
# of queries: 165 |
| 17 |
Correct |
479 ms |
1400 KB |
# of queries: 15721 |
| 18 |
Correct |
471 ms |
1272 KB |
# of queries: 15574 |
| 19 |
Correct |
479 ms |
1476 KB |
# of queries: 15615 |
| 20 |
Correct |
421 ms |
1256 KB |
# of queries: 14710 |
| 21 |
Correct |
399 ms |
1272 KB |
# of queries: 13823 |
| 22 |
Correct |
483 ms |
1308 KB |
# of queries: 15755 |
| 23 |
Correct |
483 ms |
1324 KB |
# of queries: 15718 |
| 24 |
Correct |
155 ms |
760 KB |
# of queries: 7033 |
| 25 |
Correct |
486 ms |
1276 KB |
# of queries: 15343 |
| 26 |
Correct |
411 ms |
1272 KB |
# of queries: 14341 |
| 27 |
Correct |
159 ms |
760 KB |
# of queries: 7116 |
| 28 |
Correct |
202 ms |
692 KB |
# of queries: 6043 |
| 29 |
Correct |
194 ms |
760 KB |
# of queries: 6039 |
| 30 |
Correct |
200 ms |
760 KB |
# of queries: 6043 |
