Submission #259570

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
259570	2020-08-08T02:47:30 Z	tqbfjotld	Santa Claus (RMI19_santa)	C++14	20 / 100	1000 ms	5624 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];

map<int,multiset<int> > thing;

bool test(int d,int bound){
    multiset<int> presents;
    if (thing.count(d)){

    }
    else{
        multiset<int> presents2;
        for (int x = 0; x<d; x++){
            if (iself[x]){
                presents2.insert(val[x]);
            }
            else{
                auto it = presents2.lower_bound(val[x]);
                if (it!=presents2.end()) {
                    presents2.erase(it);
                }
            }
        }
        thing[d] = presents2;
    }
    for (auto x : thing[d]){
        presents.insert(x);
    }
    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--){
        thing.clear();
        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:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&T);
     ~~~~~^~~~~~~~~
santa.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&n);
         ~~~~~^~~~~~~~~
santa.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&pos[x]);
             ~~~~~^~~~~~~~~~~~~~
santa.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&t);
             ~~~~~^~~~~~~~~
santa.cpp:78: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	1081 ms	3748 KB	Time limit exceeded
4	Execution timed out	1078 ms	5624 KB	Time limit exceeded
5	Execution timed out	1087 ms	4216 KB	Time limit exceeded
6	Execution timed out	1083 ms	940 KB	Time limit exceeded
7	Execution timed out	1080 ms	1688 KB	Time limit exceeded
8	Execution timed out	1085 ms	1528 KB	Time limit exceeded
9	Execution timed out	1068 ms	2688 KB	Time limit exceeded
10	Execution timed out	1087 ms	2604 KB	Time limit exceeded