Submission #75187

#TimeUsernameProblemLanguageResultExecution timeMemory
75187vexmedians (balkan11_medians)C++14
100 / 100
40 ms4572 KiB
#include <bits/stdc++.h> #define maxn 100005 using namespace std; int n; bool bio[2*maxn]; int sol[2*maxn]; int tree[2*maxn]; int najm,najv; int query(int k) { int s = 0; while (k >= 1) { s += tree[k]; k -= k&-k; } return s; } void update(int k) { while (k <= 2*n-1) { tree[k] ++; k += k&-k; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n; najm=1; najv=2*n-1; for(int i=1;i<=2*n-1;i++)bio[i]=false; cin>>sol[0]; bio[sol[0]]=true; update(sol[0]); for(int i=1;i<n;i++) { int x; cin>>x; int uk=2*i-1; int man=query(x-1); int vec=uk-man; if(!bio[x]) { sol[uk]=x; uk++; bio[x]=true; update(x); if(vec>man) { while(bio[najm])najm++; sol[uk]=najm; update(najm); bio[najm]=true; najm++; uk++; } else{ while(bio[najv])najv--; sol[uk]=najv; update(najv); bio[najv]=true; najv--; uk++; } } else{ for(int j=0;j<2;j++) { if(vec>man) { while(bio[najm])najm++; sol[uk]=najm; update(najm); bio[najm]=true; najm++; man++; uk++; } else{ while(bio[najv])najv--; sol[uk]=najv; update(najv); bio[najv]=true; najv--; vec++; uk++; } } } } for(int i=0;i<2*n-1;i++)cout<<sol[i]<<" "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...