This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
struct node{
vector<int> a;
int l, r;
};
vector<node> v;
vector<int> M;
void combine(int x){
fill(M.begin(), M.end(), 0);
M[v[0].r-1] = M[v[x].l-1] = 1;
int tmp = Query(M);
if (tmp==1){
v[0].a.push_back(v[x].l);
v[0].r = v[x].l;
v.erase(v.begin()+x);
}
else{
v[0].a.insert(v[0].a.begin(), v[x].l);
v[0].l = v[x].l;
v.erase(v.begin()+x);
}
}
int bi_search(int l, int r){
if (r-l==1) return l;
int m = (l+r)>>1;
fill(M.begin(), M.end(), 0);
for (auto &x:v[0].a) M[x-1] = 1;
for (int i=l;i<m;i++){
for (auto &x:v[i].a) M[x-1] = 1;
}
int val1 = Query(M);
for (auto &x:v[0].a) M[x-1] = 0;
int val2 = Query(M);
if (val1-val2==1) return bi_search(m, r);
return bi_search(l, m);
}
void Solve(int N){
v.resize(N);
M.resize(N, 0);
for (int i=0;i<N;i++){
v[i].a.push_back(i+1);
v[i].l = v[i].r = i+1;
}
for (int i=N;i>1;i--){
int tmp = bi_search(1, i);
combine(tmp);
}
Answer(v[0].a);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |