Submission #231497

#	Time	Username	Problem	Language	Result	Execution time	Memory
231497		summitwei	medians (balkan11_medians)	C++17	100 / 100	71 ms	3820 KiB

medians

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long double ld;

#define F0R(i, a) for(int i=0; i<a; i++)
#define FOR(i, a, b) for(int i=a; i<=b; i++)
#define RFOR(i, b, a) for(int i=b; i>=a; i--)

#define f first
#define s second
#define pb push_back
#define INF 0x3f3f3f3f
#define MOD 998244353LL

#define MN 200005
int n;
int b[MN];
vi a;
bool used[MN];

int main(){
    cin >> n;
    FOR(i, 1, n){
        cin >> b[i];
    }
    used[b[1]] = true;
    a.pb(b[1]);
    int l=1, r=2*n-1;
    FOR(i, 2, n){
        if(b[i] == b[i-1]){
            while(used[l]) ++l;
            while(used[r]) --r;
            a.pb(l);
            a.pb(r);
            used[l] = used[r] = true;
        } else if(b[i] < b[i-1]){
            if(used[b[i]]){
                while(used[l]) ++l;
                a.pb(l); used[l] = true;
                while(used[l]) ++l;
                a.pb(l); used[l] = true;
            } else{
                a.pb(b[i]);
                used[b[i]] = true;
                while(used[l]) ++l;
                a.pb(l); used[l] = true;
            }
        } else{
            if(used[b[i]]){
                while(used[r]) --r;
                a.pb(r); used[r] = true;
                while(used[r]) --r;
                a.pb(r); used[r] = true;
            } else{
                a.pb(b[i]);
                used[b[i]] = true;
                while(used[r]) --r;
                a.pb(r); used[r] = true;
            }
        }
    }
    for(auto u : a) cout << u << " ";
    cout << "\n";

    return 0;
}

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