Submission #259632

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
259632	2020-08-08T05:54:07 Z	cheeheng	Santa Claus (RMI19_santa)	C++14	0 / 100	1000 ms	4348 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];
bool taken[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]);
        }

        memset(taken, false, sizeof(taken));

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

        if(maxElfIndx == -1){
            for(int i = 0; i < N; i ++){
                printf("-1\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:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &T);
     ~~~~~^~~~~~~~~~
santa.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &N);
         ~~~~~^~~~~~~~~~
santa.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &X[i]);
             ~~~~~^~~~~~~~~~~~~
santa.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &H[i]);
             ~~~~~^~~~~~~~~~~~~
santa.cpp:73: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	19 ms	768 KB	Output isn't correct
2	Incorrect	163 ms	768 KB	Output isn't correct
3	Execution timed out	1092 ms	896 KB	Time limit exceeded
4	Execution timed out	1092 ms	896 KB	Time limit exceeded
5	Execution timed out	1094 ms	1144 KB	Time limit exceeded
6	Execution timed out	1096 ms	1536 KB	Time limit exceeded
7	Execution timed out	1091 ms	1792 KB	Time limit exceeded
8	Execution timed out	1087 ms	2432 KB	Time limit exceeded
9	Execution timed out	1098 ms	4216 KB	Time limit exceeded
10	Execution timed out	1087 ms	4348 KB	Time limit exceeded