| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58197 |
2018-07-17T06:28:12 Z |
김세빈(#1689) |
Library (JOI18_library) |
C++11 |
|
324 ms |
720 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 |
31 ms |
376 KB |
Output is correct |
| 2 |
Correct |
18 ms |
376 KB |
Output is correct |
| 3 |
Correct |
30 ms |
376 KB |
Output is correct |
| 4 |
Correct |
21 ms |
376 KB |
Output is correct |
| 5 |
Correct |
29 ms |
416 KB |
Output is correct |
| 6 |
Correct |
31 ms |
548 KB |
Output is correct |
| 7 |
Correct |
23 ms |
548 KB |
Output is correct |
| 8 |
Correct |
28 ms |
548 KB |
Output is correct |
| 9 |
Correct |
28 ms |
548 KB |
Output is correct |
| 10 |
Correct |
20 ms |
548 KB |
Output is correct |
| 11 |
Correct |
2 ms |
548 KB |
Output is correct |
| 12 |
Correct |
2 ms |
548 KB |
Output is correct |
| 13 |
Correct |
2 ms |
548 KB |
Output is correct |
| 14 |
Correct |
2 ms |
572 KB |
Output is correct |
| 15 |
Correct |
3 ms |
572 KB |
Output is correct |
| 16 |
Correct |
5 ms |
572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
376 KB |
Output is correct |
| 2 |
Correct |
18 ms |
376 KB |
Output is correct |
| 3 |
Correct |
30 ms |
376 KB |
Output is correct |
| 4 |
Correct |
21 ms |
376 KB |
Output is correct |
| 5 |
Correct |
29 ms |
416 KB |
Output is correct |
| 6 |
Correct |
31 ms |
548 KB |
Output is correct |
| 7 |
Correct |
23 ms |
548 KB |
Output is correct |
| 8 |
Correct |
28 ms |
548 KB |
Output is correct |
| 9 |
Correct |
28 ms |
548 KB |
Output is correct |
| 10 |
Correct |
20 ms |
548 KB |
Output is correct |
| 11 |
Correct |
2 ms |
548 KB |
Output is correct |
| 12 |
Correct |
2 ms |
548 KB |
Output is correct |
| 13 |
Correct |
2 ms |
548 KB |
Output is correct |
| 14 |
Correct |
2 ms |
572 KB |
Output is correct |
| 15 |
Correct |
3 ms |
572 KB |
Output is correct |
| 16 |
Correct |
5 ms |
572 KB |
Output is correct |
| 17 |
Correct |
324 ms |
720 KB |
Output is correct |
| 18 |
Correct |
232 ms |
720 KB |
Output is correct |
| 19 |
Correct |
208 ms |
720 KB |
Output is correct |
| 20 |
Correct |
205 ms |
720 KB |
Output is correct |
| 21 |
Correct |
210 ms |
720 KB |
Output is correct |
| 22 |
Correct |
259 ms |
720 KB |
Output is correct |
| 23 |
Correct |
294 ms |
720 KB |
Output is correct |
| 24 |
Correct |
88 ms |
720 KB |
Output is correct |
| 25 |
Correct |
207 ms |
720 KB |
Output is correct |
| 26 |
Correct |
185 ms |
720 KB |
Output is correct |
| 27 |
Correct |
80 ms |
720 KB |
Output is correct |
| 28 |
Correct |
54 ms |
720 KB |
Output is correct |
| 29 |
Correct |
58 ms |
720 KB |
Output is correct |
| 30 |
Correct |
74 ms |
720 KB |
Output is correct |
