Submission #1212421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212421		yanb	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	67 ms	3024 KiB

Main

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;

int n, m;
string ans;
vector<int> s, f;

int update(int id, int l, int r) {
    while (id < m && l <= f[id] && f[id] <= r) {
        id++;
    }
    return id;
}

bool check(int x) {
    vector<int> dp(n + 1);
    vector<char> p(n + 1, 'L');
    for (int i = 0; i < n; i++) {
        dp[i + 1] = dp[i];

        int upl = update(dp[i], s[i] - x, s[i]);
        if (dp[i + 1] < upl) {
            dp[i + 1] = upl;
            p[i + 1] = 'L';
        }

        int upr = update(dp[i], s[i], s[i] + x);
        if (dp[i + 1] < upr) {
            dp[i + 1] = upr;
            p[i + 1] = 'R';
        }

        if (i > 0) {
            int uplr = update(dp[i - 1], s[i] - x, s[i - 1] + x);
            if (dp[i + 1] < uplr) {
                dp[i + 1] = uplr;
                p[i + 1] = 'B';
            }
        }
    }

    int id = n;
    while (id) {
        if (p[id] == 'L') {
            ans[id - 1] = 'L';
            id--;
        } else if (p[id] == 'R') {
            ans[id - 1] = 'R';
            id--;
        } else {
            ans[id - 2] = 'R';
            ans[id - 1] = 'L';
            id -= 2;
        }
    }

    return dp[n] == m;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> m;
    s.resize(n);
    f.resize(m);
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < m; i++) cin >> f[i];

    for (int i = 0; i < n; i++) ans += '_';

    int l = -1, r = 1e10;
    while (r - l > 1) {
        int md = (r + l) / 2;
        if (check(md)) {
            r = md;
        } else {
            l = md;
        }
    }

    if (r == 1e10) {
        cout << "-1\n";
    } else {
        check(r);
        cout << r << "\n" << ans << "\n";
    }
}

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