oj.uz

Submission #101420

# Submission time Handle Problem Language Result Execution time Memory
101420 2019-03-19T01:29:30 Z errorgorn Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 5760 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];
vector<ii> v;
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;
    }
}
int main(){
    //freopen("input.txt","r",stdin);
    vector<ii>::iterator it;
    int a,b;
    scanf("%d%d",&n,&d);
    d--;
    for (int x=0;x<n;x++){
        scanf("%d",&arr[x]);
    }
    scanf("%d",&q);
    while (q--){
        getchar();
        if (getchar()=='E'){
            scanf("%d%d",&a,&b);
            v.push_back(ii(a-1,b-1));
            E++;
        }
        else{
            scanf("%d",&a);
            v.push_back(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);
    if (true){
        for (it=v.begin();it!=v.end();it++){
            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;
            }
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:71:9: warning: unused variable 'tb' [-Wunused-variable]
     int tb=min(n,10);
         ^~
cake.cpp:49: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:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:58: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:63: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 384 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 1099 ms 4612 KB Output isn't correct
2 Incorrect 198 ms 4580 KB Output isn't correct
3 Incorrect 724 ms 4584 KB Output isn't correct
4 Correct 100 ms 4708 KB Output is correct
5 Execution timed out 2049 ms 4712 KB Time limit exceeded
6 Incorrect 1596 ms 4716 KB Output isn't correct
7 Incorrect 1703 ms 4708 KB Output isn't correct
8 Correct 142 ms 4580 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2050 ms 2016 KB Time limit exceeded
2 Execution timed out 2054 ms 2060 KB Time limit exceeded
3 Execution timed out 2041 ms 1912 KB Time limit exceeded
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 2056 ms 2540 KB Time limit exceeded
6 Execution timed out 2057 ms 2656 KB Time limit exceeded
7 Execution timed out 2031 ms 2572 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 1020 KB Output isn't correct
2 Incorrect 227 ms 1044 KB Output isn't correct
3 Execution timed out 2047 ms 1648 KB Time limit exceeded
4 Execution timed out 2037 ms 1676 KB Time limit exceeded
5 Incorrect 303 ms 2540 KB Output isn't correct
6 Execution timed out 2049 ms 2824 KB Time limit exceeded
7 Incorrect 1903 ms 2692 KB Output isn't correct
8 Execution timed out 2037 ms 2896 KB Time limit exceeded
9 Execution timed out 2023 ms 5632 KB Time limit exceeded
10 Incorrect 901 ms 5760 KB Output isn't correct
11 Execution timed out 2048 ms 4956 KB Time limit exceeded
12 Execution timed out 2041 ms 5536 KB Time limit exceeded
13 Execution timed out 2044 ms 5680 KB Time limit exceeded