Submission #1328404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1328404		arman.khachatryan	medians (balkan11_medians)	C++20	10 / 100	1095 ms	2672 KiB

medians

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    int b[n+2], a[2*n+2], c[2*n+2], j, k;
    bool bl[2*n+2]={}, used[2*n+2]={};
    for(int i=1; i<=2*n-1; i++){
        c[i]=i;
    }
    for(int i=1; i<=n; i++){
        cin>>b[i];
        bl[b[i]]=true;
    }
    a[1]=b[1];
    j=2;
    for(int i=2; i<=2*n-1; i+=2){
        a[i]=b[j];
        j++;
        if(j>n){
            break;
        }
    }
    j=1;
    k=2*n-1;
    for(int i=2; i<=2*n-1; i+=2){
        if(i==2 && !used[a[i]]){
            if(a[i]>a[i-1]){
                while(bl[c[k]]){
                    k--;
                }
                a[i+1]=c[k];
            }else{
                while(bl[c[j]]){
                    j++;
                }
                a[i+1]=c[j];
            }
        }else if(!used[a[i]]){
            if(a[i]>a[i-2]){
                while(bl[c[k]]){
                    k--;
                }
                a[i+1]=c[k];
            }else{
                while(bl[c[j]]){
                    j++;
                }
                a[i+1]=c[j];
            }
        }else{
            int t=i-1, cnt=0;
            while(a[t]!=a[i]){
                if(a[t]<a[i]){
                    cnt++;
                }else{
                    cnt--;
                }
                t--;
            }
            if(cnt==2){
                while(bl[c[k]]){
                    k--;
                }
                a[i]=c[k];
                while(bl[c[k]]){
                    k--;
                }
                a[i+1]=c[k];
            }else if(cnt==0){
                while(bl[c[j]]){
                    j++;
                }
                a[i]=c[j];
                while(bl[c[j]]){
                    j++;
                }
                a[i+1]=c[j];
            }else{
                while(bl[c[k]]){
                    k--;
                }
                a[i]=c[k];
                while(bl[c[j]]){
                    j++;
                }
                a[i+1]=c[j];
            }
        }
        bl[a[i]]=true;
        bl[a[i+1]]=true;
        used[a[i]]=true;
        used[a[i+1]]=true;
    }
    for(int i=1; i<2*n; i++){
        cout<<a[i]<<" ";
    }
}

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