Submission #674048

#	Time	Username	Problem	Language	Result	Execution time	Memory
674048		Ahmed57	medians (balkan11_medians)	C++14	5 / 100	63 ms	8012 KiB

medians

#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;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--<<" ";
        }
    }
}

• Subtask 1: 5 / 65
• Subtask 2: 0 / 35