Submission #104115

#TimeUsernameProblemLanguageResultExecution timeMemory
104115faustaadpmedians (balkan11_medians)C++17
0 / 100
137 ms15412 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define fi first #define se second typedef long long ll; using namespace std; ll n,i,a[202020],b[202020],sud[202020],jaw[202020],j; set<ll> st; int main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin>>n; for(i=1;i<=n;i++)cin>>a[i]; for(i=1;i<n;i++)b[a[i]]++; for(i=1;i<=n*2-1;i++) if(b[i]==0) st.insert(i); jaw[1]=a[1]; for(i=n-1;i>=1;i--) { if(a[i]>a[i+1]) { j=*st.upper_bound(a[i]); b[j]=1; sud[j]=1; jaw[i*2]=j; st.erase(j); j=*st.upper_bound(a[i]); b[j]=1; sud[j]=1; jaw[i*2+1]=j; st.erase(j); } else if(a[i]<a[i+1]) { j=*st.lower_bound(a[i]); b[j]=1; sud[j]=1; jaw[i*2]=j; st.erase(j); j=*st.lower_bound(a[i]); b[j]=1; sud[j]=1; jaw[i*2+1]=j; st.erase(j); } else { j=*st.lower_bound(a[i]); b[j]=1; sud[j]=1; jaw[i*2]=j; st.erase(j); j=*st.upper_bound(a[i]); b[j]=1; sud[j]=1; jaw[i*2+1]=j; st.erase(j); } b[a[i]]--; if(b[a[i]]==0&&sud[a[i]]==0)st.insert(a[i]); } for(i=1;i<=(n*2-1);i++) if(i<(n*2-1)) cout<<jaw[i]<<" "; else cout<<jaw[i]<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...