제출 #480728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
480728		kawaii	medians (balkan11_medians)	C++14	100 / 100	111 ms	14896 KiB

medians

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

int n, b[100005], a[200005], tree[200005];
set<int> s;

void update(int u){
    while(u <= n * 2 - 1){
        tree[u] += 1;
        u += (u & -u);
    }    
}

int get(int u){
    int res = 0;
    while(u > 0){
        res += tree[u];
        u -= (u & -u);
    }
    return res;
}

void solve(){
    for(int i = 1; i <= 2 * n - 1; i++) s.insert(i);
    s.erase(b[1]);
    update(b[1]);
    a[1] = b[1];
    for(int i = 2; i <= n; i++){
        int smaller = get(b[i] - 1);
        int bigger = 2 * i - 3 - smaller;
        if(s.find(b[i]) == s.end()) bigger--;
        else; 
        if(smaller - bigger == -2){
            a[2 * i - 2] = *s.begin();
            s.erase(a[2 * i - 2]);
            update(a[2 * i - 2]);
            a[2 * i - 1] = *s.begin();
            s.erase(a[2 * i - 1]);
            update(a[2 * i - 1]);
        }
        else if(smaller - bigger == -1){
            a[2 * i - 2] = b[i];
            s.erase(a[2 * i - 2]);
            update(a[2 * i - 2]);
            a[2 * i - 1] = *s.begin();
            s.erase(a[2 * i - 1]);
            update(a[2 * i - 1]);
        }
        else if(smaller - bigger == 0){
            a[2 * i - 2] = *s.begin();
            s.erase(a[2 * i - 2]);
            update(a[2 * i - 2]);
            a[2 * i - 1] = *s.rbegin();
            s.erase(a[2 * i - 1]);
            update(a[2 * i - 1]);
        }
        else if(smaller - bigger == 1){
            a[2 * i - 2] = b[i];
            s.erase(a[2 * i - 2]);
            update(a[2 * i - 2]);
            a[2 * i - 1] = *s.rbegin();
            s.erase(a[2 * i - 1]);
            update(a[2 * i - 1]);
        }
        else{
            a[2 * i - 2] = *s.rbegin();
            s.erase(a[2 * i - 2]);
            update(a[2 * i - 2]);
            a[2 * i - 1] = *s.rbegin();
            s.erase(a[2 * i - 1]);
            update(a[2 * i - 1]);
        }
    }
    for(int i = 1; i <= 2 * n - 1; i++) cout << a[i] <<" ";
}
 
signed main(){ 
    //freopen("medians.in", "r", stdin);
    //freopen("medians.out", "w", stdout);
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> b[i];
    solve();
}

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