oj.uz

Submission #480728

# Submission time Handle Problem Language Result Execution time Memory
480728 2021-10-18T01:17:12 Z kawaii medians (balkan11_medians) C++14
100 / 100
 111 ms 14896 KB 
#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.0 / 65.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 4 ms 844 KB Output is correct
3 Correct 8 ms 1448 KB Output is correct
4 Correct 14 ms 2628 KB Output is correct
5 Correct 34 ms 4972 KB Output is correct
6 Correct 67 ms 9560 KB Output is correct
7 Correct 111 ms 14896 KB Output is correct