oj.uz

Submission #101417

# Submission time Handle Problem Language Result Execution time Memory
101417 2019-03-19T01:27:59 Z errorgorn Cake (CEOI14_cake) C++14
0 / 100
 1873 ms 11636 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 (n<=10000 && q<=10000){
        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 1077 ms 8808 KB Output isn't correct
2 Incorrect 222 ms 8944 KB Output isn't correct
3 Incorrect 795 ms 8860 KB Output isn't correct
4 Correct 109 ms 8796 KB Output is correct
5 Incorrect 137 ms 9084 KB Output isn't correct
6 Incorrect 135 ms 9452 KB Output isn't correct
7 Incorrect 186 ms 9316 KB Output isn't correct
8 Incorrect 94 ms 9436 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 3184 KB Output isn't correct
2 Incorrect 29 ms 3184 KB Output isn't correct
3 Incorrect 35 ms 3064 KB Output isn't correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 85 ms 4720 KB Output isn't correct
6 Incorrect 72 ms 4724 KB Output isn't correct
7 Incorrect 43 ms 4848 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 1548 KB Output isn't correct
2 Incorrect 201 ms 1404 KB Output isn't correct
3 Incorrect 23 ms 2544 KB Output isn't correct
4 Incorrect 21 ms 2552 KB Output isn't correct
5 Incorrect 294 ms 3564 KB Output isn't correct
6 Incorrect 46 ms 4332 KB Output isn't correct
7 Incorrect 1873 ms 4196 KB Output isn't correct
8 Incorrect 72 ms 4968 KB Output isn't correct
9 Incorrect 131 ms 11620 KB Output isn't correct
10 Incorrect 964 ms 8176 KB Output isn't correct
11 Incorrect 119 ms 8860 KB Output isn't correct
12 Incorrect 132 ms 11020 KB Output isn't correct
13 Incorrect 173 ms 11636 KB Output isn't correct