| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 80717 |
2018-10-22T04:32:03 Z |
admin |
Library (JOI18_library) |
C++17 |
|
243 ms |
832 KB |
#include "library.h"
#include <bits/stdc++.h>
using namespace std;
vector <vector <int>> G;
int g;
void Solve(int N)
{
int i, j, cnt, q;
vector <int> ask(N);
for(i=0;i<N;i++){
for(j=0;j<=i;j++) ask[j] = 1;
q = Query(ask);
for(j=0;j<=i;j++) ask[j] = 0;
if(q == g + 1){
// new group
vector <int> v = {i};
G.push_back(v);
g ++;
}
else if(g == q){
// endpoint
int k, b;
k = 0;
ask[i] = 1;
for(b=0;(1<<b)<g;b++){
cnt = 0;
for(j=0;j<g;j++) if(j & (1 << b)){
for(auto &t: G[j]) ask[t] = 1;
cnt ++;
}
q = Query(ask);
if(q == cnt) k |= 1 << b;
for(j=0;j<g;j++) if(j & (1 << b)){
for(auto &t: G[j]) ask[t] = 0;
}
}
ask[i] = 0;
for(auto &t: G[k]) ask[t] = 1;
ask[G[k].back()] = 0;
ask[i] = 1;
q = Query(ask);
if(q == 1) reverse(G[k].begin(), G[k].end());
G[k].push_back(i);
for(auto &t: G[k]) ask[t] = 0;
ask[i] = 0;
}
else{
// merge two groups
int k1, k2, t1, t2, b, f, f1, f2, nf;
k1 = k2 = f1 = f2 = nf = 0; f = -1;
ask[i] = 1;
for(b=0;(1<<b)<g;b++){
cnt = 0;
for(j=0;j<g;j++) if(j & (1 << b)){
for(auto &t: G[j]) ask[t] = 1;
cnt ++;
}
q = Query(ask);
if(q == cnt - 1) k1 |= 1 << b, k2 |= 1 << b;
else if(q == cnt){
if(f == -1) k1 |= 1 << b, f = 0;
else f |= 1 << b;
}
else nf |= 1 << b;
for(j=0;j<g;j++) if(j & (1 << b)){
for(auto &t: G[j]) ask[t] = 0;
}
}
ask[i] = 0;
if(f != -1){
ask[i] = 1;
for(b=0;(1<<b)<g;b++) if(f & (1 << b)){
cnt = 0;
for(j=0;j<g;j++) if((j & k1) == k1 && (j & nf) == 0 && (j & (1 << b))){
t1 = j; t2 = k2 | ((~j) & f);
if(t2 >= g) continue;
for(auto &t: G[t1]) ask[t] = 1;
for(auto &t: G[t2]) ask[t] = 1;
cnt += 2;
}
q = Query(ask);
if(q == cnt - 1) f1 |= 1 << b;
else f2 |= 1 << b;
for(j=0;j<g;j++) if((j & k1) == k1 && (j & nf) == 0 && (j & (1 << b))){
t1 = j; t2 = k2 | ((~j) & f);
if(t2 >= g) continue;
for(auto &t: G[t1]) ask[t] = 0;
for(auto &t: G[t2]) ask[t] = 0;
}
}
ask[i] = 0;
}
k1 |= f1; k2 |= f2;
if(k1 >= g || k2 >= g) while(1);
for(auto &t: G[k1]) ask[t] = 1;
ask[G[k1].back()] = 0;
ask[i] = 1;
q = Query(ask);
if(q == 1) reverse(G[k1].begin(), G[k1].end());
for(auto &t: G[k1]) ask[t] = 0;
ask[i] = 0;
for(auto &t: G[k2]) ask[t] = 1;
ask[G[k2].back()] = 0;
ask[i] = 1;
q = Query(ask);
if(q == 2) reverse(G[k2].begin(), G[k2].end());
for(auto &t: G[k2]) ask[t] = 0;
ask[i] = 0;
G[k1].push_back(i);
for(auto &t: G[k2]) G[k1].push_back(t);
G[k2].clear(); swap(G[k2], G.back());
G.pop_back();
g --;
}
}
for(auto &t : G[0]) t ++;
Answer(G[0]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
316 KB |
# of queries: 1151 |
| 2 |
Correct |
14 ms |
356 KB |
# of queries: 1172 |
| 3 |
Correct |
17 ms |
412 KB |
# of queries: 1210 |
| 4 |
Correct |
21 ms |
416 KB |
# of queries: 1233 |
| 5 |
Correct |
20 ms |
432 KB |
# of queries: 1207 |
| 6 |
Correct |
24 ms |
436 KB |
# of queries: 1229 |
| 7 |
Correct |
22 ms |
624 KB |
# of queries: 1246 |
| 8 |
Correct |
15 ms |
624 KB |
# of queries: 1174 |
| 9 |
Correct |
15 ms |
624 KB |
# of queries: 1199 |
| 10 |
Correct |
12 ms |
624 KB |
# of queries: 707 |
| 11 |
Correct |
2 ms |
624 KB |
# of queries: 1 |
| 12 |
Correct |
2 ms |
624 KB |
# of queries: 3 |
| 13 |
Correct |
2 ms |
624 KB |
# of queries: 5 |
| 14 |
Correct |
2 ms |
624 KB |
# of queries: 8 |
| 15 |
Correct |
2 ms |
624 KB |
# of queries: 48 |
| 16 |
Correct |
3 ms |
624 KB |
# of queries: 104 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
316 KB |
# of queries: 1151 |
| 2 |
Correct |
14 ms |
356 KB |
# of queries: 1172 |
| 3 |
Correct |
17 ms |
412 KB |
# of queries: 1210 |
| 4 |
Correct |
21 ms |
416 KB |
# of queries: 1233 |
| 5 |
Correct |
20 ms |
432 KB |
# of queries: 1207 |
| 6 |
Correct |
24 ms |
436 KB |
# of queries: 1229 |
| 7 |
Correct |
22 ms |
624 KB |
# of queries: 1246 |
| 8 |
Correct |
15 ms |
624 KB |
# of queries: 1174 |
| 9 |
Correct |
15 ms |
624 KB |
# of queries: 1199 |
| 10 |
Correct |
12 ms |
624 KB |
# of queries: 707 |
| 11 |
Correct |
2 ms |
624 KB |
# of queries: 1 |
| 12 |
Correct |
2 ms |
624 KB |
# of queries: 3 |
| 13 |
Correct |
2 ms |
624 KB |
# of queries: 5 |
| 14 |
Correct |
2 ms |
624 KB |
# of queries: 8 |
| 15 |
Correct |
2 ms |
624 KB |
# of queries: 48 |
| 16 |
Correct |
3 ms |
624 KB |
# of queries: 104 |
| 17 |
Correct |
197 ms |
624 KB |
# of queries: 7855 |
| 18 |
Correct |
192 ms |
624 KB |
# of queries: 7819 |
| 19 |
Correct |
243 ms |
696 KB |
# of queries: 7846 |
| 20 |
Correct |
179 ms |
832 KB |
# of queries: 7336 |
| 21 |
Correct |
168 ms |
832 KB |
# of queries: 6959 |
| 22 |
Correct |
202 ms |
832 KB |
# of queries: 7913 |
| 23 |
Correct |
228 ms |
832 KB |
# of queries: 7856 |
| 24 |
Correct |
69 ms |
832 KB |
# of queries: 3666 |
| 25 |
Correct |
190 ms |
832 KB |
# of queries: 7706 |
| 26 |
Correct |
206 ms |
832 KB |
# of queries: 7260 |
| 27 |
Correct |
74 ms |
832 KB |
# of queries: 3619 |
| 28 |
Correct |
80 ms |
832 KB |
# of queries: 1999 |
| 29 |
Correct |
47 ms |
832 KB |
# of queries: 1997 |
| 30 |
Correct |
54 ms |
832 KB |
# of queries: 1999 |
