#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 = 0; i < 10; 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 = 0; i < 10; 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);
}
res.clear();
for(auto v: piles){
while(!v.empty()){
res.pb(v.front());
v.pop_front();
}
}
Answer(res);
}
Compilation message
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 |
| 1 |
Incorrect |
10 ms |
344 KB |
Wrong Answer [8] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
344 KB |
Wrong Answer [8] |
| 2 |
Halted |
0 ms |
0 KB |
- |
