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 "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=86005;
int lo[MAXN],hi[MAXN],arr[MAXN],res[MAXN],n,bit[MAXN];
vector<int> mid[MAXN];
int query(int now){
int ret=0;
for(int i=now;i>0;i-=(i&(-i)))ret+=bit[i];
return ret;
}
void update(int now,int val){
for(int i=now;i<=n;i+=(i&(-i)))bit[i]+=val;
}
int binser(int x){
int now=0;
for(int i=17;i>=0;i--){
if(now+(1<<i)<=n && bit[now+(1<<i)]<x){
now+=(1<<i);
x-=bit[now];
}
}
return now+1;
}
int tengah(int x,int y){
int L=query(x-1)+1,R=query(y),T;
T=(3*L+2*R)/5; //angka 1 ke T
return binser(T); //idx angka 1 ke T
}
void Solve(int N) {
int prev=0,tmpL=1,tmpR=N+1,nxt,sudah=0,C=0;
n=N;
vector<int> v;
for(int i=1;i<=2*N;i++)v.push_back(i);
random_shuffle(v.begin(),v.end());
for(auto i : v){
if(tmpL==N+1 || Query(i)==prev){
arr[tmpR]=i;
lo[tmpR]=C+1;
hi[tmpR]=tmpL-1;
if(lo[tmpR]<hi[tmpR])mid[tengah(lo[tmpR],hi[tmpR])].push_back(tmpR);
else{
Answer(i,arr[tmpL-1]);
update(tmpL-1,-1);
arr[tmpL-1]=0;
sudah++;
}
tmpR++;
if(tmpL==tmpR-N)C=tmpL-1;
}
else{
update(tmpL,1);
arr[tmpL]=i;
tmpL++;
prev++;
}
}
int prefix=0;
while(sudah<N){
for(int i=1;i<=N;i++){
if(arr[i])prev=Query(arr[i]);
while(!mid[i].empty()){
int now=mid[i].back();
mid[i].pop_back();
nxt=Query(arr[now]);
if(prefix){
if(nxt==prev){ //sudah ada
hi[now]=i;
res[now]=i;
if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
else{
sudah++;
res[now]=binser(query(hi[now]));
Answer(arr[now],arr[res[now]]);
update(res[now],-1);
arr[res[now]]=0;
}
}
else{
lo[now]=i+1;
if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
else{
sudah++;
res[now]=binser(query(hi[now]));
Answer(arr[now],arr[res[now]]);
update(res[now],-1);
arr[res[now]]=0;
}
}
}
else{
if(nxt==prev){
lo[now]=i+1;
if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
else{
sudah++;
res[now]=binser(query(hi[now]));
Answer(arr[now],arr[res[now]]);
update(res[now],-1);
arr[res[now]]=0;
}
}
else{
hi[now]=i;
res[now]=i;
if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
else{
sudah++;
res[now]=binser(query(hi[now]));
Answer(arr[now],arr[res[now]]);
update(res[now],-1);
arr[res[now]]=0;
}
}
}
if(sudah==N)return;
prev=nxt;
}
}
prefix=1-prefix;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |