oj.uz

Submission #24809

# Submission time Handle Problem Language Result Execution time Memory
24809 2017-06-14T08:25:21 Z Extazy medians (balkan11_medians) C++14
5 / 100
 300 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,right=2*n,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=0,right=pos,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 Execution timed out 300 ms 5092 KB Execution timed out
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 6 ms 5092 KB Not a permutation
4 Incorrect 16 ms 5092 KB Not a permutation
5 Incorrect 43 ms 5092 KB Not a permutation
6 Incorrect 73 ms 5092 KB Not a permutation
7 Incorrect 143 ms 5092 KB Not a permutation