oj.uz

Submission #101403

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

using namespace std;

typedef pair<int, int> ii;

int d[250005];

int o[250005];

int N, a;

set<ii> di;

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<ii> temp;
    for(int i = 1; i < pos; i ++){
        ii temp2 = *(--di.end());
        di.erase(temp2);
        temp.insert(ii(temp2.first+1, temp2.second));
        d[temp2.second] = temp2.first+1;
    }
    ii temp3 = *(--di.end());
    d[a] = temp3.first+1;
    temp.insert(ii(temp3.first+1, a));
    for(ii x: temp){
        di.insert(x);
    }

    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 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:64: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:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &op);
         ~~~~~^~~~~~~~~~~~
cake.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
cake.cpp:84: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 Correct 3 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 Execution timed out 2051 ms 9080 KB Time limit exceeded
2 Execution timed out 2065 ms 8528 KB Time limit exceeded
3 Execution timed out 2054 ms 7704 KB Time limit exceeded
4 Execution timed out 2065 ms 8824 KB Time limit exceeded
5 Execution timed out 2058 ms 5104 KB Time limit exceeded
6 Execution timed out 2056 ms 5208 KB Time limit exceeded
7 Execution timed out 2049 ms 4912 KB Time limit exceeded
8 Execution timed out 2057 ms 5368 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 7672 KB Output is correct
2 Incorrect 91 ms 7672 KB Output isn't correct
3 Correct 85 ms 7672 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Correct 394 ms 17192 KB Output is correct
6 Incorrect 353 ms 17100 KB Output isn't correct
7 Correct 160 ms 17016 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 275 ms 2180 KB Output isn't correct
2 Correct 236 ms 2364 KB Output is correct
3 Execution timed out 2051 ms 5500 KB Time limit exceeded
4 Execution timed out 2043 ms 5224 KB Time limit exceeded
5 Incorrect 439 ms 5392 KB Output isn't correct
6 Execution timed out 2099 ms 5948 KB Time limit exceeded
7 Correct 1767 ms 7764 KB Output is correct
8 Execution timed out 2033 ms 7380 KB Time limit exceeded
9 Execution timed out 2024 ms 16252 KB Time limit exceeded
10 Incorrect 1362 ms 16860 KB Output isn't correct
11 Execution timed out 2024 ms 5668 KB Time limit exceeded
12 Execution timed out 2017 ms 13296 KB Time limit exceeded
13 Execution timed out 2051 ms 16256 KB Time limit exceeded