oj.uz

Submission #101437

# Submission time Handle Problem Language Result Execution time Memory
101437 2019-03-19T02:01:11 Z cheeheng Cake (CEOI14_cake) C++14
35 / 100
 2000 ms 14840 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 13 ms 384 KB Output is correct
5 Correct 102 ms 1032 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2035 ms 896 KB Time limit exceeded
2 Execution timed out 2036 ms 896 KB Time limit exceeded
3 Execution timed out 2032 ms 896 KB Time limit exceeded
4 Execution timed out 2005 ms 896 KB Time limit exceeded
5 Execution timed out 2070 ms 1712 KB Time limit exceeded
6 Execution timed out 2017 ms 1664 KB Time limit exceeded
7 Execution timed out 2037 ms 1664 KB Time limit exceeded
8 Execution timed out 2048 ms 1664 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 6520 KB Output is correct
2 Correct 126 ms 6392 KB Output is correct
3 Correct 92 ms 6332 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 371 ms 14840 KB Output is correct
6 Correct 370 ms 14736 KB Output is correct
7 Correct 157 ms 14536 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 668 KB Output is correct
2 Correct 257 ms 888 KB Output is correct
3 Execution timed out 2021 ms 3576 KB Time limit exceeded
4 Execution timed out 2016 ms 3456 KB Time limit exceeded
5 Correct 510 ms 760 KB Output is correct
6 Execution timed out 2019 ms 4348 KB Time limit exceeded
7 Correct 1994 ms 1528 KB Output is correct
8 Execution timed out 2013 ms 5752 KB Time limit exceeded
9 Execution timed out 2023 ms 14196 KB Time limit exceeded
10 Correct 1663 ms 1712 KB Output is correct
11 Execution timed out 2063 ms 1816 KB Time limit exceeded
12 Execution timed out 2013 ms 11592 KB Time limit exceeded
13 Execution timed out 2061 ms 14464 KB Time limit exceeded