Submission #443552

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
443552	2021-07-10T18:37:04 Z	valerikk	Santa Claus (RMI19_santa)	C++17	30 / 100	1000 ms	3708 KB

santa

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

const int N = 96068 + 123;

int n;
int x[N], type[N], val[N];
int res[N];

bool check(int l, int r) {
    for (int i = r + 1; i < n; i++) {
        if (type[i] == 0) {
            return false;
        }
    }
    multiset<int> s;
    for (int i = 0; i < l; i++) {
        if (type[i] == 0) {
            s.insert(val[i]);
        } else {
            auto it = s.lower_bound(val[i]);
            if (it != s.end()) {
                s.erase(it);
            }
        }
    }
    vector<int> a, b;
    for (int t : s) {
        a.push_back(t);
    }
    for (int i = l; i <= r; i++) {
        if (type[i] == 0) {
            a.push_back(val[i]);
        } else {
            b.push_back(val[i]);
        }
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    if (a.size() > b.size()) {
        return false;
    }
    for (int i = 0; i < a.size(); i++) {
        if (a[i] < b[i]) {
            return false;
        }
    }
    return true;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> type[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> val[i];
    }
    int l = -1, r = n;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (check(0, mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    for (int i = 0; i < r; i++) {
        res[i] = -1;
    }
    if (r != n) {
        l = 0;
        for (; r < n; r++) {
            while (l < r && check(l + 1, r)) {
                l++;
            }
            res[r] = 2 * x[r] - x[l];
        }
    }
    for (int i = 0; i < n; i++) {
        cout << res[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Compilation message

santa.cpp: In function 'bool check(int, int)':
santa.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	332 KB	Output is correct
2	Correct	5 ms	328 KB	Output is correct
3	Correct	445 ms	512 KB	Output is correct
4	Execution timed out	1092 ms	776 KB	Time limit exceeded
5	Execution timed out	1095 ms	800 KB	Time limit exceeded
6	Execution timed out	1076 ms	848 KB	Time limit exceeded
7	Execution timed out	1089 ms	1460 KB	Time limit exceeded
8	Execution timed out	1090 ms	2076 KB	Time limit exceeded
9	Execution timed out	1078 ms	3520 KB	Time limit exceeded
10	Execution timed out	1089 ms	3708 KB	Time limit exceeded