| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 537436 |
2022-03-15T05:59:00 Z |
chaoyue |
Library (JOI18_library) |
C++14 |
|
465 ms |
208 KB |
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int n;
vector<int> v;
int findedge(){
int m, l=0, r=(int)v.size()-1;
vector<int> ma(n, 0), mb(n, 0); //ma is query array for a, mb is query array for b
for(int i=0; i<(int)v.size(); i++){
ma[v[i]] = 1;
}
while(r > l){
//cut a in half and get result
m = (l + r) / 2; //2nd half of a will be discarded, 1st half (including split) will be included
for(int i=m+1; i<=r; i++){
ma[v[i]] = 0;
mb[v[i]] = 1;
}
if(Query(ma) >= Query(mb)){ //take remain
r = m;
}
else{ //take discarded
for(int i=m+1; i<=r; i++){
ma[v[i]] = 1;
mb[v[i]] = 0;
}
for(int i=l; i<=m; i++){
ma[v[i]] = 0;
mb[v[i]] = 1;
}
l = m+1;
}
}
return v[l];
}
void Solve(int N){
n = N;
int tmp, l=0, r=n-1;
vector<int> ans(n), m(n, 0);
v.resize(n);
for(int i=0; i<n; i++){
v[i] = i;
}
for(int i=0; i<n; i++){
tmp = findedge();
//cout<<"tmp: "<<tmp<<endl;
v.erase(find(v.begin(), v.end(), tmp));
if(!l){
ans[l] = tmp;
l++;
}
else{
//Query l and tmp
m[ans[l-1]] = 1;
m[tmp] = 1;
if(Query(m) == 1){
m[ans[l-1]] = 0;
ans[l] = tmp;
l++;
}
else{
m[ans[l-1]] = 0;
ans[r] = tmp;
r--;
}
m[tmp] = 0;
}
}
for(int i=0; i<n; i++){
ans[i]++;
}
Answer(ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
208 KB |
# of queries: 2585 |
| 2 |
Correct |
34 ms |
208 KB |
# of queries: 2548 |
| 3 |
Correct |
55 ms |
208 KB |
# of queries: 2719 |
| 4 |
Correct |
47 ms |
208 KB |
# of queries: 2705 |
| 5 |
Correct |
37 ms |
208 KB |
# of queries: 2717 |
| 6 |
Correct |
34 ms |
208 KB |
# of queries: 2723 |
| 7 |
Correct |
34 ms |
208 KB |
# of queries: 2727 |
| 8 |
Correct |
38 ms |
208 KB |
# of queries: 2596 |
| 9 |
Correct |
38 ms |
208 KB |
# of queries: 2700 |
| 10 |
Correct |
17 ms |
208 KB |
# of queries: 1600 |
| 11 |
Correct |
1 ms |
208 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
208 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
208 KB |
# of queries: 8 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 13 |
| 15 |
Correct |
3 ms |
208 KB |
# of queries: 98 |
| 16 |
Correct |
3 ms |
208 KB |
# of queries: 214 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
208 KB |
# of queries: 2585 |
| 2 |
Correct |
34 ms |
208 KB |
# of queries: 2548 |
| 3 |
Correct |
55 ms |
208 KB |
# of queries: 2719 |
| 4 |
Correct |
47 ms |
208 KB |
# of queries: 2705 |
| 5 |
Correct |
37 ms |
208 KB |
# of queries: 2717 |
| 6 |
Correct |
34 ms |
208 KB |
# of queries: 2723 |
| 7 |
Correct |
34 ms |
208 KB |
# of queries: 2727 |
| 8 |
Correct |
38 ms |
208 KB |
# of queries: 2596 |
| 9 |
Correct |
38 ms |
208 KB |
# of queries: 2700 |
| 10 |
Correct |
17 ms |
208 KB |
# of queries: 1600 |
| 11 |
Correct |
1 ms |
208 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
208 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
208 KB |
# of queries: 8 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 13 |
| 15 |
Correct |
3 ms |
208 KB |
# of queries: 98 |
| 16 |
Correct |
3 ms |
208 KB |
# of queries: 214 |
| 17 |
Correct |
461 ms |
208 KB |
# of queries: 18171 |
| 18 |
Correct |
435 ms |
208 KB |
# of queries: 17934 |
| 19 |
Correct |
465 ms |
208 KB |
# of queries: 18213 |
| 20 |
Correct |
398 ms |
208 KB |
# of queries: 16963 |
| 21 |
Correct |
351 ms |
208 KB |
# of queries: 15914 |
| 22 |
Correct |
384 ms |
208 KB |
# of queries: 18211 |
| 23 |
Correct |
347 ms |
208 KB |
# of queries: 18206 |
| 24 |
Correct |
149 ms |
208 KB |
# of queries: 8318 |
| 25 |
Correct |
380 ms |
208 KB |
# of queries: 17724 |
| 26 |
Correct |
367 ms |
208 KB |
# of queries: 16590 |
| 27 |
Correct |
126 ms |
208 KB |
# of queries: 8298 |
| 28 |
Correct |
454 ms |
208 KB |
# of queries: 18953 |
| 29 |
Correct |
440 ms |
208 KB |
# of queries: 18932 |
| 30 |
Correct |
453 ms |
208 KB |
# of queries: 18953 |
