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 <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ordered_set s;
int n;cin>>n;
int l = 1 , r = 2*n-1;
int vis[2*n] = {0};
for(int i = 1;i<=n;i++){
long long x;cin>>x;
if(i==1){
cout<<x<<" ";
s.insert(x);
vis[x] = 1;
continue;
}
int c = s.order_of_key(x);
int rem = (2*(i-1)-1)-c;
if(vis[x])rem--;
if(c>rem){
vis[x] = 1;
while(vis[r])r--;
s.insert(r);
s.insert(x);
vis[r] = 1;
cout<<r--<<" ";
cout<<x<<" ";
}else if(rem>c){
vis[x] = 1;
while(vis[l])l++;
s.insert(l);
s.insert(x);
vis[l] = 1;
cout<<l++<<" ";
cout<<x<<" ";
}else{
while(vis[l])l++;
while(vis[r])r--;
vis[l] = 1;
vis[r] = 1;
s.insert(l);
s.insert(r);
cout<<l++<<" ";
cout<<r--<<" ";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |