oj.uz

답안 #480727

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480727 2021-10-18T01:15:59 Z kawaii 중앙값 배열 (balkan11_medians) C++14
0 / 100
 3 ms 400 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();
}

Compilation message

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.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
2 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
3 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
4 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
5 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
6 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
7 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
8 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
9 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
10 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
11 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
12 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
13 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected

Subtask #2
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
2 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
3 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
4 Incorrect 2 ms 400 KB Unexpected end of file - int32 expected
5 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected
6 Incorrect 3 ms 332 KB Unexpected end of file - int32 expected
7 Incorrect 2 ms 332 KB Unexpected end of file - int32 expected