oj.uz

Submission #262223

# Submission time Handle Problem Language Result Execution time Memory
262223 2020-08-12T13:41:00 Z LifeHappen__ medians (balkan11_medians) C++14
100 / 100
 33 ms 6264 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define forinc(a,b,c) for(int a=b, _=c; a<=_; ++a)
#define fordec(a,b,c) for(int a=b, _=c; a>=_; --a)
#define forv(a,b) for(auto &a:b)
#define rep(i,n) forinc(i,1,n)
#define repv(i,n) forinc(i,0,n-1)

#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define gcd __gcd
#define __builtin_popcount __builtin_popcountll
#define fasty ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define bit(x, i) (x >> (i) & 1ll)
#define on(x, i) (x | (1ll << (i - 1)))
#define off(x, i) (x & ~(1ll << (i - 1)))

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;

const int N=2e5+5;
int n,a[N],b[N],dd[N];
int st,en;
void pre(int pos){
    while(dd[st]) st++;
    b[pos]=st;
    dd[st]=1;
}
void suf(int pos){
    while(dd[en]) en--;
    b[pos]=en;
    dd[en]=1;
}

int32_t main(){
    fasty;
    cin>>n;
    forinc(i,1,n) cin>>a[i];
    dd[a[1]]=1;
    b[1]=a[1];
    st=1, en=2*n-1;
    forinc(i,2,n){
        if(a[i]==a[i-1]) pre(2*i-2), suf(2*i-1);
        else if(a[i]>a[i-1]){
            if(!dd[a[i]]){
                dd[a[i]]=1;
                b[2*i-2]=a[i];
                suf(2*i-1);
            }else{
                suf(2*i-2); suf(2*i-1);
            }
        } else{
            if(!dd[a[i]]){
                dd[a[i]]=1;
                b[2*i-2]=a[i];
                pre(2*i-1);
            } else pre(2*i-2), pre(2*i-1);
        }
    }
    forinc(i,1,2*n-1) cout<<b[i]<<' ';
}

Subtask #1
65.0 / 65.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 4 ms 768 KB Output is correct
4 Correct 6 ms 1280 KB Output is correct
5 Correct 12 ms 2176 KB Output is correct
6 Correct 27 ms 4088 KB Output is correct
7 Correct 33 ms 6264 KB Output is correct