Submission #1312975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312975		zbyszko	medians (balkan11_medians)	C++20	100 / 100	143 ms	20864 KiB

medians

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using ll = long long;
using pii = pair<ull,ull>;
#define x first
#define y second

set<int> us;

void zm(int& a,int& b){
    while(us.find(a)!=us.end()) a++;
    while(us.find(b)!=us.end()) b--;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;cin >> n;
    vector<int> med(n);
    for(int& i:med){
        cin >> i;
        us.insert(i);
    }
    set<int> usv;
    int l=1,r=2*n-1;
    zm(l,r);
    cout << med[0] << " ";
    usv.insert(med[0]);
    for(int i=1;i<n;i++){
        //cout << i << ": " << l << " " << r << endl;
        if(usv.find(med[i])!=usv.end()){
            if(med[i]==med[i-1]){
                cout << l << " " << r << " ";
                us.insert(l);
                us.insert(r);
                usv.insert(l);
                usv.insert(r);
                zm(l,r);
            }
            else if(med[i]>med[i-1]){
                cout << r << " ";
                us.insert(r);
                usv.insert(r);
                zm(l,r);
                cout << r << " ";
                us.insert(r);
                usv.insert(r);
                zm(l,r);
            }
            else{
                cout << l << " ";
                us.insert(l);
                usv.insert(l);
                zm(l,r);
                cout << l << " ";
                us.insert(l);
                usv.insert(l);
                zm(l,r);
            }
        }
        else if(med[i]>med[i-1]){
            cout << med[i] << " " << r << " ";
            us.insert(r);
            usv.insert(r);
            usv.insert(med[i]);
            zm(l,r);
        }
        else{
            cout << med[i] << " " << l << " ";
            us.insert(l);
            usv.insert(l);
            usv.insert(med[i]);
            zm(l,r);
        }
    }
    return 0;
}

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