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;
#define f first
#define s second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
vector<deque<int>> piles;
vector<int> pile_range(int l, int r){
vector<int> res(n, 0);
for(int i = l; i <= r; i++){
for(auto v: piles[i]) res[v-1] = 1;
}
return res;
}
int query_range(int l, int r, int el){
vector<int> check = pile_range(l, r);
check[el-1] = 1;
return Query(check);
}
void merge1(int l, int r, int el){
// 11 queries at most
int il = l, ir = r;
while(ir-il+1 > 1){
int mid = (il + ir) / 2;
int q = query_range(il, mid, el);
if(q == mid-il+1) ir = mid;
else il = mid+1;
}
vector<int> check(n, 0);
check[el-1] = 1, check[piles[il].front()-1] = 1;
int q = Query(check);
if(q == 1) piles[il].push_front(el);
else piles[il].push_back(el);
}
void merge2(int l, int r, int el){
// 22 queries at most
int il = l, ir = r;
if(ir < il) return;
for(int i = 9; i >= 0; i--){
int im = il + (1 << i);
if(im >= ir) continue;
int q = query_range(im, ir, el);
if(q == ir-im) il = im;
}
for(int i = 9; i >= 0; i--){
int im = ir - (1 << i);
if(im <= il) continue;
int q = query_range(il, im, el);
if(q == im-il) ir = im;
}
bool il_front = false, ir_front = false;
vector<int> check(n, 0);
check[el-1] = 1, check[piles[il].front()-1] = 1;
int q = Query(check);
if(q == 1) il_front = true;
check = vector<int>(n, 0);
check[el-1] = 1, check[piles[ir].front()-1] = 1;
q = Query(check);
if(q == 1) ir_front = true;
if(il_front && ir_front){
piles[il].push_front(el);
while(!piles[ir].empty()){
piles[il].push_front(piles[ir].front());
piles[ir].pop_front();
}
}
if(il_front && !ir_front){
piles[il].push_front(el);
while(!piles[ir].empty()){
piles[il].push_front(piles[ir].back());
piles[ir].pop_back();
}
}
if(!il_front && ir_front){
piles[il].push_back(el);
while(!piles[ir].empty()){
piles[il].push_back(piles[ir].front());
piles[ir].pop_front();
}
}
if(!il_front && !ir_front){
piles[il].push_back(el);
while(!piles[ir].empty()){
piles[il].push_back(piles[ir].back());
piles[ir].pop_back();
}
}
piles.erase(piles.begin() + ir);
}
void Solve(int N){
n = N;
vector<int> elements(N), res(N);
iota(elements.begin(), elements.end(), 1);
// shuffle(elements.begin(), elements.end(), rng);
piles.pb({elements[0]});
for(int i = 1; i < N; i++){
int el = elements[i], q, m;
q = query_range(0, piles.size()-1, el);
if(q == piles.size()+1){
piles.pb({el});
continue;
}
if(q == piles.size()) merge1(0, piles.size()-1, el);
if(q == piles.size()-1) merge2(0, piles.size()-1, el);
// cout << "Piles: " << endl;
// for(auto v: piles){
// for(auto u: v){
// cout << u << " ";
// }
// cout << endl;
// }
}
res.clear();
for(auto v: piles){
while(!v.empty()){
res.pb(v.front());
v.pop_front();
}
}
for(auto v: res){
cout << v << " ";
}
Answer(res);
}
Compilation message (stderr)
library.cpp: In function 'void Solve(int)':
library.cpp:131:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | if(q == piles.size()+1){
| ~~^~~~~~~~~~~~~~~~~
library.cpp:136:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | if(q == piles.size()) merge1(0, piles.size()-1, el);
| ~~^~~~~~~~~~~~~~~
library.cpp:137:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | if(q == piles.size()-1) merge2(0, piles.size()-1, el);
| ~~^~~~~~~~~~~~~~~~~
library.cpp:127:28: warning: unused variable 'm' [-Wunused-variable]
127 | int el = elements[i], q, m;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |