#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;
}
}
vector<int> now = vec;
now[r] = 1;
if(ask(vec) == ask(now)) 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 |
Incorrect |
54 ms |
376 KB |
Wrong Answer [6] |
| 2 |
Correct |
44 ms |
376 KB |
# of queries: 2189 |
| 3 |
Correct |
40 ms |
560 KB |
# of queries: 2325 |
| 4 |
Correct |
47 ms |
376 KB |
# of queries: 2264 |
| 5 |
Incorrect |
44 ms |
376 KB |
Wrong Answer [8] |
| 6 |
Correct |
54 ms |
504 KB |
# of queries: 2300 |
| 7 |
Incorrect |
50 ms |
472 KB |
Wrong Answer [6] |
| 8 |
Incorrect |
56 ms |
376 KB |
Wrong Answer [6] |
| 9 |
Correct |
55 ms |
376 KB |
# of queries: 2311 |
| 10 |
Incorrect |
31 ms |
400 KB |
Wrong Answer [6] |
| 11 |
Correct |
5 ms |
248 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
376 KB |
# of queries: 2 |
| 13 |
Incorrect |
6 ms |
376 KB |
Wrong Answer [8] |
| 14 |
Correct |
5 ms |
376 KB |
# of queries: 7 |
| 15 |
Correct |
6 ms |
376 KB |
# of queries: 63 |
| 16 |
Incorrect |
9 ms |
248 KB |
Wrong Answer [6] |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
376 KB |
Wrong Answer [6] |
| 2 |
Correct |
44 ms |
376 KB |
# of queries: 2189 |
| 3 |
Correct |
40 ms |
560 KB |
# of queries: 2325 |
| 4 |
Correct |
47 ms |
376 KB |
# of queries: 2264 |
| 5 |
Incorrect |
44 ms |
376 KB |
Wrong Answer [8] |
| 6 |
Correct |
54 ms |
504 KB |
# of queries: 2300 |
| 7 |
Incorrect |
50 ms |
472 KB |
Wrong Answer [6] |
| 8 |
Incorrect |
56 ms |
376 KB |
Wrong Answer [6] |
| 9 |
Correct |
55 ms |
376 KB |
# of queries: 2311 |
| 10 |
Incorrect |
31 ms |
400 KB |
Wrong Answer [6] |
| 11 |
Correct |
5 ms |
248 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
376 KB |
# of queries: 2 |
| 13 |
Incorrect |
6 ms |
376 KB |
Wrong Answer [8] |
| 14 |
Correct |
5 ms |
376 KB |
# of queries: 7 |
| 15 |
Correct |
6 ms |
376 KB |
# of queries: 63 |
| 16 |
Incorrect |
9 ms |
248 KB |
Wrong Answer [6] |
| 17 |
Correct |
502 ms |
1404 KB |
# of queries: 15898 |
| 18 |
Correct |
485 ms |
1372 KB |
# of queries: 15757 |
| 19 |
Incorrect |
497 ms |
1412 KB |
Wrong Answer [6] |
| 20 |
Incorrect |
472 ms |
1444 KB |
Wrong Answer [6] |
| 21 |
Incorrect |
410 ms |
1332 KB |
Wrong Answer [6] |
| 22 |
Correct |
483 ms |
1272 KB |
# of queries: 15940 |
| 23 |
Incorrect |
530 ms |
1404 KB |
Wrong Answer [6] |
| 24 |
Incorrect |
159 ms |
760 KB |
Wrong Answer [6] |
| 25 |
Incorrect |
563 ms |
1316 KB |
Wrong Answer [6] |
| 26 |
Correct |
441 ms |
1452 KB |
# of queries: 14516 |
| 27 |
Incorrect |
169 ms |
764 KB |
Wrong Answer [6] |
| 28 |
Correct |
240 ms |
760 KB |
# of queries: 6034 |
| 29 |
Correct |
214 ms |
664 KB |
# of queries: 6030 |
| 30 |
Correct |
199 ms |
888 KB |
# of queries: 6034 |
