Submission #415494

#TimeUsernameProblemLanguageResultExecution timeMemory
415494qwerasdfzxclLibrary (JOI18_library)C++14
100 / 100
609 ms472 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...