Submission #1167298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167298		juliany2	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	101 ms	10916 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()


int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<int> s(n), f(m);
    vector<array<int, 2>> a;
    for (int &i : s) {
        cin >> i;
        a.push_back({i, 0});
    }
    for (int &i : f) {
        cin >> i;
        if (!binary_search(all(s), i))
            a.push_back({i, 1});
    }

    sort(all(a));

    int A = a.size();

    // next sprinkler
    vector<int> nxt(A, -1);
    for (int i = A - 2; i >= 0; i--) {
        nxt[i] = (a[i + 1][1] == 0 ? i + 1 : nxt[i + 1]);
    }

    string o;
    int lo = 0, hi = 1e9, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;

        vector<int> dp(A + 1, -1);
        vector<string> used(A + 1);

        auto upd = [&](int i, int j, string c) {
            if (dp[j] == -1) {
                dp[j] = i;
                used[j] = c;
            }
        };

        dp[0] = 0;
        for (int i = 0; i < A; i++) {
            if (dp[i] == -1)
                continue;

            auto &[x, t] = a[i];

            if (t == 0) {
                int j = i + 1;
                while (j < A && a[j][1] == 1 && a[j][0] <= x + mid)
                    j++;
                upd(i, j, "R");
                continue;
            }

            if (nxt[i] != -1 && a[nxt[i]][0] <= x + mid) {
                upd(i, nxt[i] + 1, "L");

                int p = nxt[i];
                int q = nxt[p];
                if (q != -1 && a[q][0] <= x + mid) {
                    int r = nxt[q];
                    if (r != -1 && a[r][0] <= a[p][0] + mid)
                        upd(i, r, "LR");
                    else
                        upd(i, upper_bound(all(a), array<int, 2> ({a[p][0] + mid, 3})) - a.begin(), "LR");
                }
            }
        }

        /*
        cout << "check: " << mid << '\n';

        for (int i = 0; i <= A; i++)
            cout << "> " << i << ' ' << a[i][0] << ' ' << a[i][1] << " | " << nxt[i] << ' ' << dp[i] << ' ' << used[i] << '\n';
            */

        if (dp[A] != -1) {
            string dir;
            for (int i = A; i > 0; i = dp[i])
                dir += used[i];
            reverse(all(dir));
            assert(dir.size() == n);

            ans = mid, o = dir, hi = mid - 1;
        } else
            lo = mid + 1;
    }

    cout << ans << '\n';

    if (ans != -1)
        cout << o << '\n';

    return 0;
}

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