Submission #480727

#	Time	Username	Problem	Language	Result	Execution time	Memory
480727		kawaii	medians (balkan11_medians)	C++14	0 / 100	3 ms	400 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();
}

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     freopen("medians.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
medians.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     freopen("medians.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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