oj.uz

답안 #51632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51632 2018-06-19T10:49:43 Z someone_aa 중앙값 배열 (balkan11_medians) C++17
15 / 100
 93 ms 5272 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 100100;
int tree[8*maxn], b[maxn], a[2*maxn], n;
bool used[2*maxn];

void update(int x, int li=0, int ri=2*n,int index=1) {
    if(li==ri) tree[index] = 1;
    else {
        int mid = (li+ri) /2;
        if(x <= mid) update(x, li, mid, 2*index);
        else if(x > mid) update(x, mid+1, ri, 2*index+1);

        tree[index] = tree[2*index] + tree[2*index+1];
    }
}

int query(int ql, int qr, int li=0, int ri=2*n, int index=1) {
    if(qr < ql) return 0;
    if(li > qr || ri < ql) return 0;
    else if(li >= ql && ri <= qr) return tree[index];
    else {
        int mid = (li+ri)/2;
        return query(ql,qr,li,mid,2*index) + query(ql,qr,mid+1,ri,2*index+1);
    }
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>b[i];
    }

    a[1] = b[1];
    used[b[1]] = true;

    update(b[1]);

    int st = 1, fh = 2*n-1;

    if(b[1] == 1) st = 2;
    else st = 1;

    if(b[1] == 2*n-1) fh = 2*n-2;
    else fh = 2*n-1;

    for(int i=2;i<=n;i++) {
        //cout<<i<<" -> ";
        if(used[b[i]]) {
          //  cout<<"Placing A: "<<st<<" "<<fh<<" -> ";
            a[2*(i-1)] = st;
            a[2*(i-1)+1] = fh;
            update(st); update(fh);
            used[st] = used[fh] = true;
            while(used[st] && st < 2 * n) st++;
            while(used[fh] && fh > 0) fh--;
            //cout<<st<<" "<<fh<<"\n";
        }
        else {
            //cout<<"Placing B: "<<st<<" "<<fh<<" -> ";
            a[2*(i-1)] = b[i];
            used[b[i]] = true;
            update(b[i]);
            int temp = query(1, b[i]-1);

            //cout<<temp<<" -> ";

            while(used[st] && st < 2 * n) st++;
            while(used[fh] && fh > 0) fh--;

            if(temp == (i-1)) {
              //  cout<<"Stavljam pogolemo\n";
                a[2*(i-1)+1] = fh;
                used[fh] = true;
                update(fh);
                while(used[fh] && fh > 0) fh--;
            }
            else if(temp < (i-1)) {
                //cout<<"Stavljam pomalo\n";
                a[2*(i-1)+1] = st;
                used[st] = true;
                update(st);
                while(used[st] && st < 2 * n) st++;
            }
            //cout<<st<<" "<<fh<<"\n";
        }
    }

    for(int i=1;i<=2*n-1;i++) {
        cout<<a[i]<<" ";
    }

    return 0;
}

Subtask #1
15.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 3 ms 448 KB Output isn't correct
3 Correct 2 ms 448 KB Output is correct
4 Incorrect 3 ms 468 KB Integer 0 violates the range [1, 79]
5 Incorrect 2 ms 644 KB Integer 0 violates the range [1, 99]
6 Correct 2 ms 644 KB Output is correct
7 Incorrect 2 ms 644 KB Output isn't correct
8 Incorrect 2 ms 644 KB Integer 0 violates the range [1, 159]
9 Incorrect 2 ms 644 KB Integer 0 violates the range [1, 179]
10 Incorrect 2 ms 644 KB Integer 0 violates the range [1, 199]
11 Incorrect 2 ms 644 KB Integer 0 violates the range [1, 599]
12 Incorrect 2 ms 644 KB Integer 0 violates the range [1, 1199]
13 Incorrect 3 ms 644 KB Integer 0 violates the range [1, 1999]

Subtask #2
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 644 KB Integer 0 violates the range [1, 3999]
2 Incorrect 6 ms 736 KB Integer 0 violates the range [1, 7999]
3 Incorrect 11 ms 992 KB Integer 0 violates the range [1, 15999]
4 Incorrect 25 ms 1168 KB Integer 0 violates the range [1, 31999]
5 Incorrect 39 ms 1924 KB Integer 0 violates the range [1, 63999]
6 Incorrect 61 ms 3328 KB Integer 0 violates the range [1, 127999]
7 Incorrect 93 ms 5272 KB Integer 0 violates the range [1, 199999]