Submission #170387

#TimeUsernameProblemLanguageResultExecution timeMemory
170387workharderMinerals (JOI19_minerals)C++14
100 / 100
210 ms7260 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...