Submission #674051

#	Time	Username	Problem	Language	Result	Execution time	Memory
674051		Ahmed57	medians (balkan11_medians)	C++14	100 / 100	89 ms	11716 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;
        if(vis[x])rem--;
        if(vis[x]){
            if(c>rem){
                while(vis[r])r--;
                vis[r] = 1;
                cout<<r<<" ";
                s.insert(r--);
                while(vis[r])r--;
                vis[r] = 1;
                cout<<r<<" ";
                s.insert(r--);
            }else if(c==rem){
                while(vis[l])l++;
                while(vis[r])r--;
                vis[l] = 1;
                vis[r] = 1;
                s.insert(l);
                s.insert(r);
                cout<<l++<<" ";
                cout<<r--<<" ";
            }else{
                while(vis[l])l++;
                vis[l] = 1;
                cout<<l<<" ";
                s.insert(l++);
                while(vis[l])l++;
                vis[l] = 1;
                cout<<l<<" ";
                s.insert(l++);
            }
        }else{
        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: 65 / 65
• Subtask 2: 35 / 35