Submission #337128

#TimeUsernameProblemLanguageResultExecution timeMemory
337128nandonathanielmedians (balkan11_medians)C++14
100 / 100
137 ms12524 KiB
#include<bits/stdc++.h> using namespace std; int bit[200005],n; void update(int now,int val){ for(int i=now;i<=2*n;i+=(i&(-i)))bit[i]+=val; } int query(int now){ int ret=0; for(int i=now;i>0;i-=(i&(-i)))ret+=bit[i]; return ret; } set<int> available; int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int a; cin >> n >> a; cout << a; update(a,1); for(int i=1;i<2*n;i++){ if(i!=a)available.insert(i); } for(int i=2;i<=n;i++){ cin >> a; if(available.count(a)){ cout << " " << a; update(a,1); available.erase(a); int brp=i-query(a); if(brp==0){ auto it=available.end(); --it; cout << " " << *it; update(*it,1); available.erase(it); } else{ auto it=available.begin(); cout << " " << *it; update(*it,1); available.erase(it); } } else{ int brp=i-query(a); if(brp==0){ auto it=available.end(); --it; cout << " " << *it; update(*it,1); available.erase(it); auto it2=available.end(); --it2; cout << " " << *it2; update(*it2,1); available.erase(it2); } else if(brp==1){ auto it=available.begin(); cout << " " << *it; update(*it,1); available.erase(it); auto it2=available.end(); --it2; cout << " " << *it2; update(*it2,1); available.erase(it2); } else{ auto it=available.begin(); cout << " " << *it; update(*it,1); available.erase(it); auto it2=available.begin(); cout << " " << *it2; update(*it2,1); available.erase(it2); } } } cout << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...