Submission #259635

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
259635	2020-08-08T05:59:48 Z	cheeheng	Santa Claus (RMI19_santa)	C++14	0 / 100	1000 ms	2680 KB

santa

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

typedef pair<int, int> ii;

int X[100005];
int H[100005];
int V[100005];
int D[100005];

set<ii> value;
set<ii> minValue;

bool boleh(int x, int y){
    value = set<ii>();
    minValue = set<ii>();
    for(int i = 0; i < x; i ++){
        if(H[i] == 0){
            value.insert(ii(V[i], i));
        }else if(H[i] == 1){
            auto it = value.lower_bound(ii(V[i], -1));
            if(it != value.end()){
                //taken[i] = true;
                //taken[(*it).second] = true;
                value.erase(it);
            }else{
                minValue.insert(ii(V[i], i));
            }
        }
    }

    minValue = set<ii>();

    for(int i = x; i <= y; i ++){
        if(H[i] == 0){
            value.insert(ii(V[i], i));
        }else if(H[i] == 1){
            minValue.insert(ii(V[i], i));
        }
    }

    while(!value.empty() && !minValue.empty()){
        int tempValue = (*value.begin()).first;
        int tempMinValue = (*minValue.begin()).first;

        if(tempValue >= tempMinValue){
            value.erase(value.begin());
            minValue.erase(minValue.begin());
        }else{
            break;
        }
    }

    return value.empty();
}

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

    while(T --){
        int N;
        scanf("%d", &N);

        for(int i = 0; i < N; i ++){
            scanf("%d", &X[i]);
        }
        for(int i = 0; i < N; i ++){
            scanf("%d", &H[i]);
        }
        for(int i = 0; i < N; i ++){
            scanf("%d", &V[i]);
        }

        int maxElfIndx = N-1;
        while(H[maxElfIndx] == 1 && maxElfIndx >= 0){
            maxElfIndx --;
        }

        if(maxElfIndx == -1){
            throw;
            for(int i = 0; i < N; i ++){
                printf("%d ", D[i]);
            }
            printf("\n");
            continue;
        }

        memset(D, -1, sizeof(D));
        for(int i = 0; i < N; i ++){
            if(i > maxElfIndx){
                for(int j = i; j >= 0; j --){
                    if(boleh(j, i)){
                        D[i] = 2*X[i]-X[j];
                        break;
                    }
                }
            }
        }

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

    return 0;
}

Compilation message

santa.cpp: In function 'int main()':
santa.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &T);
     ~~~~~^~~~~~~~~~
santa.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &N);
         ~~~~~^~~~~~~~~~
santa.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &X[i]);
             ~~~~~^~~~~~~~~~~~~
santa.cpp:69:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &H[i]);
             ~~~~~^~~~~~~~~~~~~
santa.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &V[i]);
             ~~~~~^~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	896 KB	Output isn't correct
2	Incorrect	144 ms	768 KB	Output isn't correct
3	Execution timed out	1085 ms	768 KB	Time limit exceeded
4	Execution timed out	1038 ms	1016 KB	Time limit exceeded
5	Execution timed out	1092 ms	1016 KB	Time limit exceeded
6	Execution timed out	1092 ms	1024 KB	Time limit exceeded
7	Execution timed out	1082 ms	1280 KB	Time limit exceeded
8	Execution timed out	1068 ms	1664 KB	Time limit exceeded
9	Execution timed out	1086 ms	2680 KB	Time limit exceeded
10	Execution timed out	1089 ms	2680 KB	Time limit exceeded