oj.uz

Submission #746300

# Submission time Handle Problem Language Result Execution time Memory
746300 2023-05-22T09:03:22 Z teo_thrash medians (balkan11_medians) C++14
100 / 100
 25 ms 3092 KB 
#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.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 9 ms 1240 KB Output is correct
6 Correct 16 ms 2028 KB Output is correct
7 Correct 25 ms 3092 KB Output is correct