oj.uz

Submission #101472

# Submission time Handle Problem Language Result Execution time Memory
101472 2019-03-19T02:54:30 Z errorgorn Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 10104 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];
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 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 ||true){
        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<n && 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();
            }
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:76:9: warning: unused variable 'tb' [-Wunused-variable]
     int tb=min(n,10);
         ^~
cake.cpp:54: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:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:63: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:68: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 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1146 ms 6800 KB Output isn't correct
2 Incorrect 189 ms 6600 KB Output isn't correct
3 Incorrect 661 ms 6748 KB Output isn't correct
4 Correct 99 ms 6520 KB Output is correct
5 Execution timed out 2033 ms 6776 KB Time limit exceeded
6 Incorrect 1504 ms 7332 KB Output isn't correct
7 Incorrect 1556 ms 6848 KB Output isn't correct
8 Correct 127 ms 7288 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2004 ms 3084 KB Time limit exceeded
2 Execution timed out 2017 ms 3200 KB Time limit exceeded
3 Execution timed out 2057 ms 3080 KB Time limit exceeded
4 Correct 2 ms 256 KB Output is correct
5 Execution timed out 2025 ms 4700 KB Time limit exceeded
6 Execution timed out 2049 ms 4748 KB Time limit exceeded
7 Execution timed out 2050 ms 4772 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 1316 KB Output isn't correct
2 Incorrect 196 ms 1156 KB Output isn't correct
3 Execution timed out 2029 ms 2304 KB Time limit exceeded
4 Execution timed out 2037 ms 2196 KB Time limit exceeded
5 Incorrect 304 ms 2956 KB Output isn't correct
6 Execution timed out 2040 ms 3704 KB Time limit exceeded
7 Incorrect 1602 ms 3980 KB Output isn't correct
8 Execution timed out 2062 ms 4856 KB Time limit exceeded
9 Execution timed out 2045 ms 10104 KB Time limit exceeded
10 Incorrect 934 ms 8440 KB Output isn't correct
11 Execution timed out 2019 ms 7152 KB Time limit exceeded
12 Execution timed out 2036 ms 9464 KB Time limit exceeded
13 Execution timed out 2040 ms 9948 KB Time limit exceeded