Submission #443552

#	Time	Username	Problem	Language	Result	Execution time	Memory
443552		valerikk	Santa Claus (RMI19_santa)	C++17	30 / 100	1095 ms	3708 KiB

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 (stderr)

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 / 100