Submission #1154201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154201		Ciprian	medians (balkan11_medians)	C++20	10 / 100	64 ms	11844 KiB

medians

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

set<int> mis;
vector<int>A;
void Mex(int n){
    for (int i = 1; i <=2*n-1; i++)
        mis.insert(i);

    for (int x : A) {
        
        if(mis.find(x)!=mis.end())mis.erase(x);
    }
}

int mex() {
    return *mis.begin();
}

void update(int new_value) {
    
    if(mis.find(new_value)!=mis.end())mis.erase(new_value);
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   // freopen("medians.in", "r", stdin);
    //freopen("medians.out", "w", stdout);
    
    int n;
    cin>>n;
    vector<int> a(n+2);
    vector<bool>check(2*n+1);
    for(int i=1; i<=n; i++)cin>>a[i];
    A.push_back(a[1]);
    check[a[1]]=true;
    Mex(n);
    
    int mx=2*n-1;
    

    for(int i=2; i<=n; i++){
        if(a[i-1]>=a[i]){
            int m=mex();
            A.push_back(m);
            update(m);
            check[m]=true;
                
            if(check[a[i]]){
                
                A.push_back(mx);
                update(mx);
                check[mx]=true;
                mx--;
            }else{
                A.push_back(a[i]);
                update(a[i]);
                check[a[i]]=true;
                
            }
            
        
            
        }else{
            if(check[a[i]]){
                int m=mex();
                A.push_back(m);
                update(m);
                A.push_back(mx);
                update(mx);
                check[m]=true;
                check[mx]=true;
                mx--;
            }else{
                
                A.push_back(a[i]);
                update(a[i]);
                A.push_back(mx);
                update(mx);
                check[a[i]]=true;
                check[mx]=true;
                mx--;
            }
        }
    }for(auto e: A){
        cout<<e<<" ";
        
    }cout<<endl;

    return 0;
}

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