Submission #101571

#	Time	Username	Problem	Language	Result	Execution time	Memory
101571		SomeoneUnknown	Cake (CEOI14_cake)	C++14	0 / 100	342 ms	5084 KiB

cake

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

ii mii(int b, int c){
    return make_pair(b,c);
}

int main(){
    int n, s;
    scanf("%d %d", &n, &s);
    int topten[12];
    topten[0] = 0; //the legendary cake of NULL, found only at the end of the world.
    for(int i = 0; i < 11; i++){
        topten[i] = -1;
    }
    int iv[n+2];
    for(int i = 1; i <= n; i++){
        scanf("%d", &iv[i]);
        if(n - iv[i] < 10){
            topten[n-iv[i]+1]=i;
        }
    }
    iv[0] = iv[n+1] = n+2;
    vector<ii> lfunentropic;
    vector<ii> rtunentropic;
    lfunentropic.push_back(mii(s, -n-6));
    rtunentropic.push_back(mii(s, -n-6));
    int lp = s-1;
    int rp = s+1;
    if(n - iv[lp] < 10) lp = 0;
    //printf("%d", n-iv[rp]);
    if(n - iv[rp] < 10) rp = n+1;
    int gp = -n-5;
    while(lp > 0 || rp <= n){
            //printf("HI");
        if(iv[lp] > iv[rp]){
            rtunentropic.push_back(mii(rp, gp)); //last value
            gp++;
            rp++;
            if(n - iv[rp] < 10) rp = n+1;
        }else{
            lfunentropic.push_back(mii(lp, gp));
            gp++;
            lp++;
            if(n - iv[lp] < 10) lp = 0;
        }
    }
    int Q;
    scanf("%d", &Q);
    for(int q = 0; q < Q; q++){
        char nl, cmd;
        scanf("%c%c", &nl, &cmd);
        int id;
        scanf("%d", &id);
        if(cmd == 'F'){
            if(id == s){
                printf("0\n");
            }else if(id < s){
                bool found = false;
                for(int i = 1; i <= min(10, n); i++){
                   // printf("X: %d %d %d\n", topten[i], s, id);
                    if(topten[i] < s && topten[i] >= id){
                        int clsest = n+1;
                        for(int j = i; j > 0; j--){
                            if(topten[j] > s) clsest = min(clsest, topten[j]);
                            //if(topten[j] < s && topten[j] > id) clsest = n+1;
                        }
                        found = true;
                        printf("%d\n",clsest-id-1);
                    break;
                    }
                }
                if(!found){
                    int h = lfunentropic.size()-1;
                    int l = 0;
                    while(h-1>l){
                        int m = (h+l)/2;
                        if(lfunentropic[m].first >= id){
                            h = m;
                        }else{
                            l = m;
                        }
                    }
                    int h2 = rtunentropic.size();
                    int l2 = 0;
                    while(h2-1>l2){
                        int m = (h2+l2)/2;
                        if(rtunentropic[m].second > lfunentropic[h].second){
                            h2 = m;
                        }else{
                            l2 = m;
                        }
                    }
                    printf("%d\n", rtunentropic[l2].first - id);
                }
            }else{
                bool found = false;
                for(int i = 1; i <= min(10, n); i++){
                    //printf("X: %d %d %d\n", topten[i], s, id);
                    if(topten[i] > s && topten[i] <= id){
                        int clsest = 0;
                        for(int j = i; j > 0; j--){
                            if(topten[j] < s) clsest = max(clsest, topten[j]);
                            //if(topten[j] > s && topten[j] < id) clsest = 0;
                        }
                        found = true;
                        printf("%d\n", id-clsest-1);
                        break;
                    }
                }
                if(!found){
                //printf("HI");
                    int h = rtunentropic.size()-1;
                    int l = 0;
                    while(h-1>l){
                        int m = (h+l)/2;
                        if(rtunentropic[m].first <= id){
                            h = m;
                        }else{
                            l = m;
                        }
                    }
                    int h2 = lfunentropic.size();
                    int l2 = 0;
                    while(h2-1>l2){
                        int m = (h2+l2)/2;
                        if(lfunentropic[m].second > lfunentropic[h].second){
                            h2 = m;
                        }else{
                            l2 = m;
                        }
                    }
                    printf("%d\n", id - lfunentropic[l2].first);
                }
            }
        }else{
            int newpos;
            scanf("%d", &newpos);
            bool found = false;
            for(int i = newpos; i <= 10; i++){
                if(topten[i] == id){
                    for(int j = i; j > newpos; j--){
                        topten[j] = topten[j-1];
                    }
                    topten[newpos] = id;
                    found = true;
                }
            }
            if(!found){
                //demote topten[10];
                if(topten[10] > s){
                    int clsest = n+1;
                    for(int i = 1; i < 10; i++){
                        if(topten[i] > s) clsest = min(clsest, topten[i]);
                    }
                    if(clsest > topten[10]){
                        rtunentropic.push_back(mii(clsest-1, q));
                    }
                }else if(topten[10] < s){
                    int clsest = 0;
                    for(int i = 1; i < 10; i++){
                        if(topten[i] < s) clsest = max(clsest, topten[i]);
                    }
                    if(clsest < topten[10]){
                        lfunentropic.push_back(mii(clsest+1, q));
                    }
                }
                if(id < s){
                    while(lfunentropic[lfunentropic.size()-2].first<=id){
                        lfunentropic.pop_back();
                    }
                    if(lfunentropic[lfunentropic.size()-2].first==id+1){
                        lfunentropic.pop_back();
                    }else{
                        lfunentropic.back().first=id+1;
                    }
                }else if(id > s){
                    while(rtunentropic[rtunentropic.size()-2].first>=id){
                        rtunentropic.pop_back();
                    }
                    if(rtunentropic[rtunentropic.size()-2].first==id-1){
                        rtunentropic.pop_back();
                    }else{
                        rtunentropic.back().first=id-1;
                    }
                }
                for(int j = 10; j > newpos; j--){
                    topten[j] = topten[j-1];
                }
                topten[newpos] = id;
                found = true;
            }
        }
    }
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &s);
     ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &iv[i]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c%c", &nl, &cmd);
         ~~~~~^~~~~~~~~~~~~~~~~~~
cake.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &id);
         ~~~~~^~~~~~~~~~~
cake.cpp:141:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &newpos);
             ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50