Submission #259566

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
259566	2020-08-08T02:41:36 Z	tqbfjotld	Santa Claus (RMI19_santa)	C++14	20 / 100	1000 ms	2936 KB

santa

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

int T;
int n;
int numelf;
int lastelf;
int pos[97000];
bool iself[97000];
int val[97000];

bool test(int d,int bound){
    multiset<int> presents;
    for (int x = 0; x<d; x++){
        if (iself[x]){
            presents.insert(val[x]);
        }
        else{
            auto it = presents.lower_bound(val[x]);
            if (it!=presents.end()) {
                presents.erase(it);
            }
        }
    }
    for (int x = d; x<=bound; x++){
        if (iself[x]){
            presents.insert(val[x]);
        }
    }
    for (int x = d; x<=bound; x++){
        if (!iself[x]){
            auto it = presents.lower_bound(val[x]);
            if (it!=presents.end()){
                presents.erase(it);
            }
        }
        if (presents.empty()) break;
    }
    //printf("test %d %d returned %d\n",d,bound,presents.empty());
    return presents.empty();
}

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        for (int x = 0; x<n; x++){
            scanf("%d",&pos[x]);
        }
        lastelf = 0;
        numelf=0;
        for (int x = 0; x<n; x++){
            int t;
            scanf("%d",&t);
            if (t){
                iself[x] = false;
            }
            else {
                iself[x] = true;
                lastelf = max(lastelf,x);
                numelf++;
            }
        }
        for (int x = 0; x<n; x++){
            scanf("%d",&val[x]);
        }
        for (int x = 0; x<n; x++){
            if (x<lastelf) {
                printf("-1 ");
                continue;
            }
            if (x<2*numelf-1){
                printf("-1 ");
                continue;
            }
            if (!test(0,x)){
                printf("-1 ");
                continue;
            }
            int l = 0;
            int r = x+1;
            while (l+1<r){
                int mid = (l+r)/2;
                if (test(mid,x)) l = mid;
                else r = mid;
            }
            printf("%d ",2*pos[x]-pos[l]);
        }
        printf("\n");
    }
}

Compilation message

santa.cpp: In function 'int main()':
santa.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&T);
     ~~~~~^~~~~~~~~
santa.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&n);
         ~~~~~^~~~~~~~~
santa.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&pos[x]);
             ~~~~~^~~~~~~~~~~~~~
santa.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&t);
             ~~~~~^~~~~~~~~
santa.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&val[x]);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	15 ms	384 KB	Output is correct
3	Execution timed out	1089 ms	632 KB	Time limit exceeded
4	Execution timed out	1095 ms	632 KB	Time limit exceeded
5	Execution timed out	1093 ms	640 KB	Time limit exceeded
6	Execution timed out	1084 ms	1024 KB	Time limit exceeded
7	Execution timed out	1090 ms	1356 KB	Time limit exceeded
8	Execution timed out	1080 ms	1664 KB	Time limit exceeded
9	Execution timed out	1085 ms	2808 KB	Time limit exceeded
10	Execution timed out	1081 ms	2936 KB	Time limit exceeded