Submission #1154263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154263		Ciprian	medians (balkan11_medians)	C++20	85 / 100	1096 ms	2384 KiB

medians

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int>A;
int lastMn, lastMx;
int mn(int m, vector<bool> &visited){
    for(int i = lastMn; i <= m; i++){
        if(!visited[i]){
            return i;
        }
    }
    return m+1;
}

int mx(int m, vector<bool> &visited){
    for(int i = lastMx; i >= 1; i--){
        if(!visited[i]){
            return i;
        }
    }
    return 0;
}


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;
    lastMx=2*n-1;
    lastMn=1;

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

    return 0;
}

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