oj.uz

Submission #101419

# Submission time Handle Problem Language Result Execution time Memory
101419 2019-03-19T01:29:03 Z dantoh000 Cake (CEOI14_cake) C++14
0 / 100
 182 ms 8184 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int main(){
    int n,a;
    scanf("%d%d",&n,&a);
    a--;
    ii d[n];
    for (int i = 0; i < n; i++) {
        scanf("%d",&d[i].first);
        d[i].second = i;
        //printf("order %d %d\n",d[i].first,d[i].second);
    }
    int q;
    scanf("%d",&q);
    int num0 = 0, num1 = 0;
    iii qu[q];
    for (int i = 0; i < q; i++){
        char x;
        scanf(" %c",&x);
        qu[i].first = x != 'E';
        if (x == 'E'){
            num0++;
            scanf("%d%d",&qu[i].second.first,&qu[i].second.second);
            qu[i].second.first--;
        }
        else{
            num1++;
            scanf("%d",&qu[i].second.first);
            qu[i].second.first--;
        }
    }
    if (n <= 10000 && q <= 10000){
        //printf("crab 1\n");
        int r[n];
        sort(d,d+n,greater<ii>());
        for (int i = 0; i < n; i++){
            //printf("%d %d\n",d[i].first,d[i].second);
            r[d[i].second] = i+1;
            //printf("%d is the %dth delicious\n",d[i].second,i);
        }
        //for (int i = 0; i < n; i++){
            //printf("%d ",r[i],i);
        //}
        //printf("\n");
        for (int i = 0; i < q; i++){
            //printf("%d %d %d\n",qu[i].first,qu[i].second.first,qu[i].second.second);
            if (qu[i].first == 0){
                int k = qu[i].second.first, e = qu[i].second.second;
                for (int i = 0; i < n; i++){
                    if (e <= r[i] && r[i] <= r[k]) r[i]++;
                }
                r[k] = e;
                //for (int i = 0; i < n; i++){
                //    printf("%d ",r[i],i);
                //}
                //printf("\n");
            }
            else{
                int vis[n]; memset(vis,0,sizeof(vis));
                int b = qu[i].second.first;
                priority_queue<ii> pq; pq.push(ii(r[a],a));
                int ans = 0;
                while (pq.top().second != b){
                    ii cur = pq.top(); pq.pop();
                    int s = cur.first, t = cur.second;
                    //printf("eating %d %d\n",s,t);
                    ans++;
                    vis[t] = 1;
                    if (t-1 >= 0 && !vis[t-1]) pq.push(ii(r[t-1],t-1));
                    if (t+1 < n && !vis[t+1]) pq.push(ii(r[t+1],t+1));
                }
                printf("%d\n",ans);
            }
        }

    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:67:25: warning: unused variable 's' [-Wunused-variable]
                     int s = cur.first, t = cur.second;
                         ^
cake.cpp:7: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:11:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&d[i].first);
         ~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&x);
         ~~~~~^~~~~~~~~~
cake.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&qu[i].second.first,&qu[i].second.second);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&qu[i].second.first);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 6272 KB Output isn't correct
2 Incorrect 131 ms 6272 KB Output isn't correct
3 Incorrect 121 ms 6272 KB Output isn't correct
4 Incorrect 179 ms 6272 KB Output isn't correct
5 Incorrect 124 ms 6400 KB Output isn't correct
6 Incorrect 121 ms 6400 KB Output isn't correct
7 Incorrect 114 ms 6400 KB Output isn't correct
8 Incorrect 112 ms 6400 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 2304 KB Output isn't correct
2 Incorrect 55 ms 2292 KB Output isn't correct
3 Incorrect 57 ms 2296 KB Output isn't correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Incorrect 52 ms 3448 KB Output isn't correct
6 Incorrect 60 ms 3576 KB Output isn't correct
7 Incorrect 49 ms 3456 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 896 KB Output isn't correct
2 Incorrect 23 ms 896 KB Output isn't correct
3 Incorrect 27 ms 1564 KB Output isn't correct
4 Incorrect 35 ms 1636 KB Output isn't correct
5 Incorrect 38 ms 2048 KB Output isn't correct
6 Incorrect 56 ms 2560 KB Output isn't correct
7 Incorrect 61 ms 2816 KB Output isn't correct
8 Incorrect 64 ms 3456 KB Output isn't correct
9 Incorrect 177 ms 8056 KB Output isn't correct
10 Incorrect 117 ms 6272 KB Output isn't correct
11 Incorrect 116 ms 6400 KB Output isn't correct
12 Incorrect 182 ms 7716 KB Output isn't correct
13 Incorrect 164 ms 8184 KB Output isn't correct