oj.uz

Submission #24811

# Submission time Handle Problem Language Result Execution time Memory
24811 2017-06-14T08:30:02 Z Extazy medians (balkan11_medians) C++14
5 / 100
 156 ms 5092 KB 
#include <bits/stdc++.h>
#define next afgqfqqfqfq
#define prev klajhgjahgjka

using namespace std;

const int N = 1<<18;

int n,a[N],b[N],it[N];

void update(int pos, int val) {
    for(;pos<2*n;pos+=pos&(-pos)) it[pos]+=val;
}

int query(int pos) {
    int ans=0;
    for(;pos>=1;pos-=pos&(-pos)) ans+=it[pos];
    return ans;
}

int query(int l, int r) {
    return query(r)-query(l-1);
}

int next(int pos) {
    int left=pos-1,right=2*n-1,middle;
    while(right-left>1) {
        middle=(left+right)>>1;
        if(query(pos,middle)==middle-pos+1) left=middle;
        else right=middle;
    }
    return right;
}

int prev(int pos) {
    int left=1,right=pos+1,middle;
    while(right-left>1) {
        middle=(left+right)>>1;
        if(query(middle,pos)==pos-middle+1) right=middle;
        else left=middle;
    }
    return left;
}

int main() {
    int i;
    
    scanf("%d", &n);
    for(i=1;i<=n;i++) {
        scanf("%d", &b[i]);
    }
    
    //Handle the first element
    a[1]=b[1];
    update(a[1],1);
    
    //Handle the second and third element
    if(b[1]!=b[2]) {
        a[2]=b[2];
        update(a[2],1);
        if(a[2]<a[1]) {
            a[3]=a[2]-1;
        }
        else {
            a[3]=a[2]+1;
        }
        update(a[3],1);
    }
    else {
        a[2]=a[1]-1;
        a[3]=a[1]+1;
        update(a[2],1);
        update(a[3],1);
    }
    
    for(i=3;i<=n;i++) {
        if(b[i]==b[i-1]) {
            a[2*(i-1)]=prev(b[i]);
            update(a[2*(i-1)],1);
            a[2*(i-1)+1]=next(b[i]);
            update(a[2*(i-1)+1],1);
        }
        else if(b[i]>b[i-1]) {
            a[2*(i-1)]=next(b[i]);
            update(a[2*(i-1)],1);
            a[2*(i-1)+1]=next(b[i]);
            update(a[2*(i-1)+1],1);
        }
        else {
            a[2*(i-1)]=prev(b[i]);
            update(a[2*(i-1)],1);
            a[2*(i-1)+1]=prev(b[i]);
            update(a[2*(i-1)+1],1);
        }
    }
    for(i=1;i<2*n;i++) {
        if(i>1) printf(" ");
        printf("%d", a[i]);
    }
    printf("\n");
    
    return 0;
}

Compilation message

medians.cpp: In function 'int main()':
medians.cpp:48:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
medians.cpp:50:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
                           ^

Subtask #1
5.0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 5092 KB Not a permutation
2 Incorrect 0 ms 5092 KB Not a permutation
3 Incorrect 0 ms 5092 KB Not a permutation
4 Incorrect 0 ms 5092 KB Not a permutation
5 Incorrect 0 ms 5092 KB Not a permutation
6 Correct 0 ms 5092 KB Output is correct
7 Incorrect 0 ms 5092 KB Not a permutation
8 Incorrect 0 ms 5092 KB Not a permutation
9 Incorrect 0 ms 5092 KB Not a permutation
10 Incorrect 0 ms 5092 KB Not a permutation
11 Incorrect 0 ms 5092 KB Not a permutation
12 Incorrect 0 ms 5092 KB Not a permutation
13 Incorrect 0 ms 5092 KB Not a permutation

Subtask #2
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 5092 KB Not a permutation
2 Incorrect 3 ms 5092 KB Not a permutation
3 Incorrect 9 ms 5092 KB Not a permutation
4 Incorrect 23 ms 5092 KB Not a permutation
5 Incorrect 53 ms 5092 KB Not a permutation
6 Incorrect 86 ms 5092 KB Not a permutation
7 Incorrect 156 ms 5092 KB Not a permutation