oj.uz

답안 #101479

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101479 2019-03-19T03:02:56 Z errorgorn 케이크 (CEOI14_cake) C++14
30 / 100
 161 ms 5240 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: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
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 46 ms 632 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 4344 KB Output is correct
2 Correct 130 ms 4348 KB Output is correct
3 Correct 118 ms 4216 KB Output is correct
4 Correct 150 ms 4316 KB Output is correct
5 Correct 121 ms 4444 KB Output is correct
6 Correct 105 ms 4464 KB Output is correct
7 Correct 103 ms 4344 KB Output is correct
8 Correct 161 ms 4296 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 2424 KB Output isn't correct
2 Incorrect 57 ms 2296 KB Output isn't correct
3 Incorrect 52 ms 2360 KB Output isn't correct
4 Correct 3 ms 256 KB Output is correct
5 Incorrect 120 ms 3704 KB Output isn't correct
6 Incorrect 114 ms 3716 KB Output isn't correct
7 Incorrect 87 ms 3448 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 768 KB Output isn't correct
2 Incorrect 19 ms 760 KB Output isn't correct
3 Incorrect 21 ms 1152 KB Output isn't correct
4 Incorrect 22 ms 1024 KB Output isn't correct
5 Incorrect 34 ms 1528 KB Output isn't correct
6 Incorrect 49 ms 1784 KB Output isn't correct
7 Incorrect 38 ms 1912 KB Output isn't correct
8 Incorrect 57 ms 2296 KB Output isn't correct
9 Incorrect 142 ms 5212 KB Output isn't correct
10 Incorrect 92 ms 4188 KB Output isn't correct
11 Incorrect 92 ms 4344 KB Output isn't correct
12 Incorrect 117 ms 4984 KB Output isn't correct
13 Incorrect 125 ms 5240 KB Output isn't correct