Submission #262223

#	Time	Username	Problem	Language	Result	Execution time	Memory
262223		LifeHappen__	medians (balkan11_medians)	C++14	100 / 100	33 ms	6264 KiB

medians

#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 / 65
• Subtask 2: 35 / 35