Submission #49960

#	Time	Username	Problem	Language	Result	Execution time	Memory
49960		mra2322001	medians (balkan11_medians)	C++14	10 / 100	120 ms	23460 KiB

medians

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100002;
const int R = 2*N;

int n, a[N], b[R], dd[R];
int d[2*N];
set <int> s;

void up(){
    for(int i = 1; i <= n; i++) d[a[i]] = 1;
    for(int i = 1; i < 2*n; i++) if(d[i]==0) s.insert(i);
}

int main(){
    ios_base::sync_with_stdio(0);
   
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    b[1] = a[1];
    dd[a[1]] = 1;
    up();
    for(int i = 2; i <= n; i++){
        if(a[i]==a[i - 1]){
            auto it = s.lower_bound(a[i]); --it;
            b[2*i-1] = *it; s.erase(*it);
            it = s.lower_bound(a[i]); b[2*i-2] = *it;
            s.erase(*it);
        }
        else if(a[i] > a[i - 1]){
            if(dd[a[i]]==0){
                b[2*i-1] = a[i];
                s.erase(a[i]);
            }
            if(b[2*i-1]==0){
                auto it = s.lower_bound(a[i]);
                b[2*i-1] = *it; s.erase(it);
            }
            auto ti = s.lower_bound(a[i]);
            b[i*2-2] = *ti; s.erase(*ti);
        }
        else{
            if(dd[a[i]]==0){
                b[2*i-1] = a[i];
                s.erase(a[i]);
            }
            if(b[2*i-1]==0){
                auto it = s.lower_bound(a[i]); --it;
                b[2*i-1] = *it; s.erase(it);
            }
            auto ti = s.lower_bound(a[i]); --ti;
            b[i*2-2] = *ti; s.erase(*ti);
        }
        dd[b[2*i-1]] = dd[b[2*i-2]] = 1;
    }
    for(int i = 1; i < 2*n; i++) cout << b[i] << " ";
}

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