Submission #746300

#	Time	Username	Problem	Language	Result	Execution time	Memory
746300		teo_thrash	medians (balkan11_medians)	C++14	100 / 100	25 ms	3092 KiB

medians

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn=1e6+3;
const int mod=1e9+7;

int n;
int b[maxn];
vector<int> a;
bool used[maxn];
ll nm=0, ng;

int nai_malko(){
    while(used[nm]){
        nm++;
    }
    used[nm]=true;

    return nm;
}

int nai_golqmo(){
    while(used[ng]){
        ng--;
    }
    used[ng]=true;

    return ng;
}

int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>n;

for(int i=0; i<=2*n+1; i++){
    used[i]=false;
}

ng=2*n;
used[nm]=used[ng]=true;


for(int i=1; i<=n; i++){
    cin>>b[i];
}

a.pb(b[1]);

used[b[1]]=true;

for(int i=2; i<=n; i++){
    if(b[i-1]==b[i]){
        int x=nai_malko();
        int y=nai_golqmo();

        used[x]=true;
        used[y]=true;

        a.pb(x);
        a.pb(y);
    }

    if(b[i]>b[i-1]){
        int seg=nai_golqmo();

        used[seg]=true;

        if(!used[b[i]]){
            a.pb(b[i]);
            used[b[i]]=true;
        }else{
            a.pb(nai_golqmo());
        }
        a.pb(seg);
    }

    if(b[i]<b[i-1]){
        int seg=nai_malko();

        if(!used[b[i]]){
            a.pb(b[i]);
            used[b[i]]=true;
        }else{
            a.pb(nai_malko());
        }
        a.pb(seg);
    }
}

for(int i: a){
    cout<<i<<" ";
}

return 0;
}

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