#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) {
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 = {1};
void solve() {
while(ans.size() < n) {
int l = 0, r = n-1;
bool valid = false;
while(l < r) {
int mid = (l + r) >> 1;
vector<int> now = vec;
for(int i = l; i <= mid; i++) now[i] = 1;
int q1 = accumulate(now.begin(), now.end(), 0) ? ask(now) : 0;
now[ans.back()-1] = 0;
int q2 = accumulate(now.begin(), now.end(), 0) ? ask(now) : 0;
if(ans.size() == 1) {
if(q1 <= q2) r = mid;
else l = mid + 1;
} else {
if(q1 < q2) r = mid;
else l = mid + 1;
}
}
for(int x : ans) if(x == r + 1) return;
vector<int> now = vec; now[r] = 1;
if(ask(now) == 1) ans.emplace_back(r + 1), vec[r] = 1;
else return;
}
}
void Solve(int _n) {
n = _n;
mpow[0] = 1;
for(int i = 1; i < N; i++) mpow[i] = mpow[i-1] * M;
vec = vector<int>(n);
vec[0] = 1;
solve();
if(ans.size() < n) {
reverse(ans.begin(), ans.end());
solve();
}
Answer(ans);
}
Compilation message
library.cpp: In function 'int ask(std::vector<int>&)':
library.cpp:16: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];
~~^~~~~~~~~~
library.cpp: In function 'void solve()':
library.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ans.size() < n) {
~~~~~~~~~~~^~~
library.cpp:27:8: warning: unused variable 'valid' [-Wunused-variable]
bool valid = false;
^~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans.size() < n) {
~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
536 KB |
# of queries: 2193 |
| 2 |
Correct |
43 ms |
504 KB |
# of queries: 2188 |
| 3 |
Correct |
51 ms |
468 KB |
# of queries: 2324 |
| 4 |
Correct |
46 ms |
376 KB |
# of queries: 2263 |
| 5 |
Incorrect |
64 ms |
376 KB |
Wrong Answer [8] |
| 6 |
Correct |
42 ms |
376 KB |
# of queries: 2299 |
| 7 |
Correct |
48 ms |
520 KB |
# of queries: 2270 |
| 8 |
Correct |
47 ms |
424 KB |
# of queries: 2154 |
| 9 |
Correct |
63 ms |
632 KB |
# of queries: 2310 |
| 10 |
Correct |
43 ms |
504 KB |
# of queries: 1309 |
| 11 |
Correct |
5 ms |
248 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
248 KB |
# of queries: 2 |
| 13 |
Incorrect |
5 ms |
376 KB |
Wrong Answer [8] |
| 14 |
Correct |
5 ms |
248 KB |
# of queries: 7 |
| 15 |
Correct |
5 ms |
248 KB |
# of queries: 62 |
| 16 |
Correct |
7 ms |
324 KB |
# of queries: 168 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
536 KB |
# of queries: 2193 |
| 2 |
Correct |
43 ms |
504 KB |
# of queries: 2188 |
| 3 |
Correct |
51 ms |
468 KB |
# of queries: 2324 |
| 4 |
Correct |
46 ms |
376 KB |
# of queries: 2263 |
| 5 |
Incorrect |
64 ms |
376 KB |
Wrong Answer [8] |
| 6 |
Correct |
42 ms |
376 KB |
# of queries: 2299 |
| 7 |
Correct |
48 ms |
520 KB |
# of queries: 2270 |
| 8 |
Correct |
47 ms |
424 KB |
# of queries: 2154 |
| 9 |
Correct |
63 ms |
632 KB |
# of queries: 2310 |
| 10 |
Correct |
43 ms |
504 KB |
# of queries: 1309 |
| 11 |
Correct |
5 ms |
248 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
248 KB |
# of queries: 2 |
| 13 |
Incorrect |
5 ms |
376 KB |
Wrong Answer [8] |
| 14 |
Correct |
5 ms |
248 KB |
# of queries: 7 |
| 15 |
Correct |
5 ms |
248 KB |
# of queries: 62 |
| 16 |
Correct |
7 ms |
324 KB |
# of queries: 168 |
| 17 |
Correct |
485 ms |
1420 KB |
# of queries: 15897 |
| 18 |
Correct |
478 ms |
1464 KB |
# of queries: 15756 |
| 19 |
Correct |
487 ms |
1464 KB |
# of queries: 15893 |
| 20 |
Correct |
459 ms |
1196 KB |
# of queries: 14881 |
| 21 |
Correct |
436 ms |
1144 KB |
# of queries: 13963 |
| 22 |
Correct |
601 ms |
1340 KB |
# of queries: 15939 |
| 23 |
Correct |
522 ms |
1288 KB |
# of queries: 15949 |
| 24 |
Correct |
233 ms |
748 KB |
# of queries: 7092 |
| 25 |
Correct |
548 ms |
1272 KB |
# of queries: 15574 |
| 26 |
Correct |
485 ms |
1232 KB |
# of queries: 14515 |
| 27 |
Correct |
164 ms |
760 KB |
# of queries: 7172 |
| 28 |
Correct |
214 ms |
684 KB |
# of queries: 6034 |
| 29 |
Correct |
196 ms |
836 KB |
# of queries: 6030 |
| 30 |
Correct |
216 ms |
608 KB |
# of queries: 6034 |
