Submission #1100535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100535		crafticat	Sprinklers (CEOI24_sprinklers)	C++17	6 / 100	851 ms	13232 KiB

Main

#include <bits/stdc++.h>

using namespace std;
template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int,int>;


vi water, flowers;
V<bool> types;
constexpr int inf = 1e9 + 7;

bool ok(int r) {
    int minP = -1;
    int nextR = -1;

    multiset<pi> data;
    for (auto x : water)
        data.insert({x, 1});
    for (auto x : flowers)
        data.insert({x, 0});

    for (auto [a,b] : data) {
        if (b == 1) {
            if (minP == -1) {
                nextR = max(nextR, a + r);
                types.push_back(true);
            }
            else {
                if (minP < a - r) return false;
                else minP = -1;
                types.push_back(false);
            }
        } else {
            if (minP == -1 && a > nextR)
                minP = a;
        }
    }
    return minP == -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, m; cin >> n >> m;
    water.resize(n);
    flowers.resize(m);

    for (int i = 0; i < n; ++i) {
        cin >> water[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> flowers[i];
    }

    int l = 0, r = inf; // Last true
    while (r > l) {
        int mid = l + (r - l) / 2;
        if (ok(mid)) {
            r = mid;
        } else
            l = mid + 1;
    }

    types.clear();
    ok(l);
    if (l == inf) {
        cout << -1;
        return 0;
    }
    if (l == 0) l++;
    cout << l << "\n";
    for (auto x : types) {
        cout << (x ? "R" : "L");
    }
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47