oj.uz

Submission #101435

# Submission time Handle Problem Language Result Execution time Memory
101435 2019-03-19T02:00:00 Z cheeheng Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 14756 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

int d[250005];

int o[250005];

int N, a;

set<ii, greater<ii> > di;
set<int> rank1;

void sim(int a){
    int l = a;
    int r = a;
    o[a] = 0;
    int cnt = 1;
    for(int i = 1; i < N; i ++){
        int tempL = l-1;
        int tempR = r+1;
        if(tempL == -1){
            r = tempR;
            o[tempR] = cnt++;
            //printf("o[%d] = %d\n", tempR, cnt-1);
        }else if(tempR == N){
            l = tempL;
            o[tempL] = cnt++;
            //printf("o[%d] = %d\n", tempL, cnt-1);
        }else if(d[tempL] < d[tempR]){
            l = tempL;
            o[tempL] = cnt++;
            //printf("o[%d] = %d\n", tempL, cnt-1);
        }else{
            r = tempR;
            o[tempR] = cnt++;
            //printf("o[%d] = %d\n", tempR, cnt-1);
        }
    }
}

void e(int a, int pos){
    set<int> rank1;

    int cnt = 0;
    printf("%d\n", pos);
    if(pos != 0){
        for(ii x: di){
            cnt ++;
            rank1.insert(x.second);
            //printf("%d %d\n", x.first, x.second);
            if(cnt == pos){break;}
        }
    }

    if(rank1.count(a)){
        // a is in the top pos
        int min1 = 1e9;
        for(int i: rank1){
            min1 = min(d[i], min1);
        }

        for(int i: rank1){
            if(i != a){
                di.erase(ii(d[i], i));
                di.insert(ii(++d[i], i));
            }else{
                di.erase(ii(d[a], a));
                di.insert(ii(min1, a));
                d[a] = min1;
            }
        }

    }else{
        // a is not in the top pos
        int min1 = 1e9;
        for(int i: rank1){
            min1 = min(d[i], min1);
        }

        for(int i: rank1){
            if(d[i] != min1){
                di.erase(ii(d[i], i));
                di.insert(ii(++d[i], i));
            }
        }

        di.erase(ii(d[a], a));
        di.insert(ii(min1+1, a));
        d[a] = min1+1;
    }

    for(int i = 0; i < N; i ++){
        //printf("d[%d] = %d\n", i, d[i]);
    }
}

int main(){
    scanf("%d%d", &N, &a);

    a --;
    for(int i = 0; i < N; i ++){
        scanf("%d", &d[i]);
        di.insert(ii(d[i], i));
    }

    int cnt = 0;
    for(ii x: di){
        cnt ++;
        rank1.insert(x.second);
        if(cnt == 10){break;}
    }

    int Q;
    scanf("%d", &Q);
    sim(a);
    for(int i = 0; i < Q; i ++){
        char op;
        scanf(" %c", &op);
        if(op == 'F'){
            int x;
            scanf("%d", &x);
            printf("%d\n", o[x-1]);
        }else{
            int b, pos;
            scanf("%d%d", &b, &pos);
            e(b-1, pos);
            sim(a);
        }
    }

    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &a);
     ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &op);
         ~~~~~^~~~~~~~~~~~
cake.cpp:124:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
cake.cpp:128:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &b, &pos);
             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2028 ms 1124 KB Time limit exceeded
2 Execution timed out 2031 ms 1292 KB Time limit exceeded
3 Execution timed out 2021 ms 1328 KB Time limit exceeded
4 Execution timed out 2035 ms 1412 KB Time limit exceeded
5 Execution timed out 2081 ms 1904 KB Time limit exceeded
6 Execution timed out 2035 ms 2040 KB Time limit exceeded
7 Execution timed out 2043 ms 2040 KB Time limit exceeded
8 Execution timed out 2021 ms 1920 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 6392 KB Output isn't correct
2 Incorrect 108 ms 6284 KB Output isn't correct
3 Incorrect 104 ms 6168 KB Output isn't correct
4 Incorrect 3 ms 256 KB Output isn't correct
5 Incorrect 423 ms 14756 KB Output isn't correct
6 Incorrect 479 ms 14752 KB Output isn't correct
7 Incorrect 174 ms 14456 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 736 KB Output isn't correct
2 Incorrect 279 ms 888 KB Output isn't correct
3 Execution timed out 2005 ms 3592 KB Time limit exceeded
4 Execution timed out 2015 ms 3452 KB Time limit exceeded
5 Incorrect 480 ms 1144 KB Output isn't correct
6 Execution timed out 2040 ms 4324 KB Time limit exceeded
7 Incorrect 1761 ms 1784 KB Output isn't correct
8 Execution timed out 2058 ms 6140 KB Time limit exceeded
9 Execution timed out 2031 ms 14388 KB Time limit exceeded
10 Incorrect 1347 ms 2304 KB Output isn't correct
11 Execution timed out 2049 ms 1944 KB Time limit exceeded
12 Execution timed out 2027 ms 11376 KB Time limit exceeded
13 Execution timed out 2020 ms 14208 KB Time limit exceeded