oj.uz

Submission #674051

# Submission time Handle Problem Language Result Execution time Memory
674051 2022-12-22T17:58:09 Z Ahmed57 medians (balkan11_medians) C++14
100 / 100
 89 ms 11716 KB 
#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.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 7 ms 1108 KB Output is correct
4 Correct 13 ms 2132 KB Output is correct
5 Correct 26 ms 3924 KB Output is correct
6 Correct 53 ms 7540 KB Output is correct
7 Correct 89 ms 11716 KB Output is correct