oj.uz

Submission #101478

# Submission time Handle Problem Language Result Execution time Memory
101478 2019-03-19T03:02:33 Z errorgorn Cake (CEOI14_cake) C++14
0 / 100
 2 ms 384 KB 
#include <cstdio>
#include <vector>
#include <utility>
#include <deque>
using namespace std;
typedef pair<int,int> ii;
int n,d,q;
int E,F;
int arr[250005],top[12];
int memo[250005];
ii query[500005];
void print(){
    for (int x=0;x<n;x++){
        printf("%d ",arr[x]);
    }
    printf("\n");
    for (int x=0;x<min(n,10);x++){
        printf("%d ",top[x]);
    }
    printf("\n");
}
int f(int i){
    if (d==i) return 0;
    else{
        int ans=1;
        ii a=ii(1000000000,-1), b=ii(1000000000,-1);
        if (d!=0) a=ii(arr[d-1],d-1);
        if (d!=n-1) b=ii(arr[d+1],d+1);
        if (a>b) swap(a,b);
        while (a.second!=i){
            //printf("%d %d\n",a.second,b.second);
            if (a.second<d){
                if (a.second!=0) a=ii(arr[a.second-1],a.second-1);
                else a=ii(1000000000,-1);
            }
            else{
                if (a.second!=n-1) a=ii(arr[a.second+1],a.second+1);
                else a=ii(1000000000,-1);
            }
            if (a>b) swap(a,b);
            ans++;
        }
        return ans;
    }
}
void memof(){
    memo[d]=0;
    int ans=1;
    ii a=ii(1000000000,-1), b=ii(1000000000,-1);
    if (d!=0) a=ii(arr[d-1],d-1);
    if (d!=n-1) b=ii(arr[d+1],d+1);
    if (a>b) swap(a,b);
    while (a.first!=1000000000){
        memo[a.second]=ans++;
        if (a.second<d){
            if (a.second!=0) a=ii(arr[a.second-1],a.second-1);
            else a=ii(1000000000,-1);
        }
        else{
            if (a.second!=n-1) a=ii(arr[a.second+1],a.second+1);
            else a=ii(1000000000,-1);
        }
        if (a>b) swap(a,b);
    }
}
void print2(){
    for (int x=0;x<n;x++){
        printf("%d ",f(x));
    }
    printf("\n\n");
}
int main(){
    freopen("input.txt","r",stdin);
    int a,b;
    scanf("%d%d",&n,&d);
    d--;
    for (int x=0;x<n;x++){
        scanf("%d",&arr[x]);
    }
    scanf("%d",&q);
    for (int x=0;x<q;x++){
        getchar();
        if (getchar()=='E'){
            scanf("%d%d",&a,&b);
            query[x]=(ii(a-1,b-1));
            E++;
        }
        else{
            scanf("%d",&a);
            query[x]=(ii(a-1,-1));
            F++;
        }
    }
    for (int x=0;x<n;x++){
        if (arr[x]>n-10) top[n-arr[x]]=x;
    }
    int tb=min(n,10);
    ii it;
    //print();
    if ( (n<=10000 && q<=10000) || F<=500){
        for (int __x=0;__x<q;__x++){
            it=query[__x];
            if ((it).second==-1){ //this is F
                printf("%d\n",f((it).first));
            }
            else{ //this is E
                arr[(it).first]=arr[top[(it).second]]+1;
                for (int x=0;x<(it).second;x++){
                    arr[top[x]]++;
                }
                int _x;
                for (_x=(it).second;_x<tb && top[_x]!=(it).first;_x++){}
                for (int x=_x;x>(it).second;x--){
                    top[x]=top[x-1];
                }
                top[(it).second]=(it).first;
                //print();
                //print2();
            }
        }
    }
    else if (E<=100){
        for (int __x=0;__x<q;__x++){
            it=query[__x];
            if ((it).second==-1){ //this is F
                printf("%d\n",memo[(it).first]);
            }
            else{ //this is E
                arr[(it).first]=arr[top[(it).second]]+1;
                for (int x=0;x<(it).second;x++){
                    arr[top[x]]++;
                }
                int _x;
                for (_x=(it).second;_x<tb && top[_x]!=(it).first;_x++){}
                for (int x=_x;x>(it).second;x--){
                    top[x]=top[x-1];
                }
                top[(it).second]=(it).first;
                memof();
            }
        }
    }
    else{
        printf("goodbye world\n");
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&d);
     ~~~~~^~~~~~~~~~~~~~
cake.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&a,&b);
             ~~~~~^~~~~~~~~~~~~~
cake.cpp:89:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
             ~~~~~^~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Incorrect 2 ms 256 KB Output isn't correct
7 Incorrect 2 ms 384 KB Output isn't correct
8 Incorrect 2 ms 384 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Incorrect 2 ms 256 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Incorrect 2 ms 256 KB Output isn't correct
8 Incorrect 2 ms 304 KB Output isn't correct
9 Incorrect 2 ms 256 KB Output isn't correct
10 Incorrect 2 ms 384 KB Output isn't correct
11 Incorrect 2 ms 256 KB Output isn't correct
12 Incorrect 2 ms 384 KB Output isn't correct
13 Incorrect 2 ms 384 KB Output isn't correct