| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 290845 |
2020-09-04T13:48:13 Z |
thebes |
Library (JOI18_library) |
C++14 |
|
232 ms |
512 KB |
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
vvi arr; vi M; int i, j, lo, hi, mid;
inline bool qu(int s,int e){
fill(M.begin(),M.end(),0);
for(int i=s;i<=e;i++){
for(auto v : arr[i]) M[v] = 1;
}
return Query(M) != e-s+1;
}
inline bool qu2(int x,int y){
fill(M.begin(),M.end(),0);
M[x]=M[y]=1;
return Query(M)==1;
}
inline vi merge(vi x,vi y){
if(qu2(x[0],y[0])){
reverse(x.begin(),x.end());
for(auto v : y) x.push_back(v);
return x;
}
else if(qu2(x.back(),y.back())){
reverse(y.begin(),y.end());
for(auto v : y) x.push_back(v);
return x;
}
else if(qu2(x.back(),y[0])){
for(auto v : y) x.push_back(v);
return x;
}
else{
for(auto v : x) y.push_back(v);
return y;
}
}
inline void mrg(int x,int y){
vi a, b;
a = arr[x], b = arr[y];
arr.erase(arr.begin()+y);
arr.erase(arr.begin()+x);
arr.insert(arr.begin()+y-1,merge(a,b));
}
void Solve(int N){
arr.resize(N); M.resize(N);
for(i=0;i<N;i++) arr[i].push_back(i);
for(i=1;i<(int)arr.size();i++){
while(i&&qu(0,i)){
lo = 1, hi = i;
while(lo<hi){
mid = (lo+hi)>>1;
if(qu(mid,i)) lo=mid+1;
else hi=mid;
}
lo--;
mrg(lo, i); i--;
}
}
for(auto &v : arr[0]) v++;
Answer(arr[0]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
380 KB |
# of queries: 1642 |
| 2 |
Correct |
21 ms |
376 KB |
# of queries: 1624 |
| 3 |
Correct |
18 ms |
376 KB |
# of queries: 1704 |
| 4 |
Correct |
27 ms |
468 KB |
# of queries: 1695 |
| 5 |
Correct |
26 ms |
384 KB |
# of queries: 1701 |
| 6 |
Correct |
25 ms |
384 KB |
# of queries: 1700 |
| 7 |
Correct |
21 ms |
376 KB |
# of queries: 1717 |
| 8 |
Correct |
25 ms |
376 KB |
# of queries: 1630 |
| 9 |
Correct |
23 ms |
384 KB |
# of queries: 1700 |
| 10 |
Correct |
12 ms |
376 KB |
# of queries: 1023 |
| 11 |
Correct |
0 ms |
256 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
256 KB |
# of queries: 2 |
| 13 |
Correct |
1 ms |
256 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
256 KB |
# of queries: 10 |
| 15 |
Correct |
2 ms |
256 KB |
# of queries: 73 |
| 16 |
Correct |
3 ms |
256 KB |
# of queries: 157 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
380 KB |
# of queries: 1642 |
| 2 |
Correct |
21 ms |
376 KB |
# of queries: 1624 |
| 3 |
Correct |
18 ms |
376 KB |
# of queries: 1704 |
| 4 |
Correct |
27 ms |
468 KB |
# of queries: 1695 |
| 5 |
Correct |
26 ms |
384 KB |
# of queries: 1701 |
| 6 |
Correct |
25 ms |
384 KB |
# of queries: 1700 |
| 7 |
Correct |
21 ms |
376 KB |
# of queries: 1717 |
| 8 |
Correct |
25 ms |
376 KB |
# of queries: 1630 |
| 9 |
Correct |
23 ms |
384 KB |
# of queries: 1700 |
| 10 |
Correct |
12 ms |
376 KB |
# of queries: 1023 |
| 11 |
Correct |
0 ms |
256 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
256 KB |
# of queries: 2 |
| 13 |
Correct |
1 ms |
256 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
256 KB |
# of queries: 10 |
| 15 |
Correct |
2 ms |
256 KB |
# of queries: 73 |
| 16 |
Correct |
3 ms |
256 KB |
# of queries: 157 |
| 17 |
Correct |
224 ms |
384 KB |
# of queries: 10781 |
| 18 |
Correct |
221 ms |
384 KB |
# of queries: 10697 |
| 19 |
Correct |
216 ms |
384 KB |
# of queries: 10770 |
| 20 |
Correct |
207 ms |
512 KB |
# of queries: 10119 |
| 21 |
Correct |
188 ms |
384 KB |
# of queries: 9529 |
| 22 |
Correct |
229 ms |
384 KB |
# of queries: 10851 |
| 23 |
Correct |
217 ms |
384 KB |
# of queries: 10785 |
| 24 |
Correct |
93 ms |
384 KB |
# of queries: 5058 |
| 25 |
Correct |
232 ms |
384 KB |
# of queries: 10532 |
| 26 |
Correct |
212 ms |
384 KB |
# of queries: 9912 |
| 27 |
Correct |
72 ms |
384 KB |
# of queries: 5026 |
| 28 |
Correct |
64 ms |
384 KB |
# of queries: 2996 |
| 29 |
Correct |
72 ms |
384 KB |
# of queries: 2993 |
| 30 |
Correct |
64 ms |
384 KB |
# of queries: 2996 |
