Submission #1147199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147199		_8_8_	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	160 ms	2228 KiB

Main

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;

const int  N = (int)1e6 + 12, MOD = 998244353, inf = (int)1e9;
int n, m, s[N], f[N], dp[N], prv[N];
char res[N];
bool check(int k) {
    // 0 - L, 1 - R, RL - 2
    auto u = [&](int i, int val, int p) {
        if(val > dp[i]) {
            dp[i] = val;
            prv[i] = p;
        }
    };
    for(int i = 0; i <= n; i++) {
        dp[i] = 0;
    }
    for(int x = 0; x <= n; x++) {
        if(x) {
            if(dp[x - 1] > dp[x]) {
                dp[x] = dp[x - 1];
                prv[x] = 0;
            }
        }
        int y = dp[x] + 1;
        if(y > m) continue;
        if(x + 1 <= n && s[x + 1] - k <= f[y] && s[x + 1] >= f[y]) {
            int it = upper_bound(f + 1, f + m + 1, s[x + 1]) - f;
            u(x + 1, it - 1, 0);
        }
        if(x + 1 <= n && s[x + 1] + k >= f[y] && s[x + 1] <= f[y]) {
            int it = upper_bound(f + 1, f + m + 1, s[x + 1] + k) - f;
            u(x + 1, it - 1, 1);
        }
        if(x + 2 <= n && ((s[x + 1] <= f[y] && s[x + 1] + k >= f[y]) || (s[x + 2] >= f[y] && s[x + 2] - k <= f[y])) && s[x + 1] + k >= s[x + 2]) {
            int it = upper_bound(f + 1, f + m + 1, s[x + 1] + k) - f;
            u(x + 2, it - 1, 2);
        }
    }
    if(dp[n] < m) return false;
    for(int i = n; i >= 1; ) {
        if(prv[i] == 2) {
            res[i - 1] = 'R';
            res[i] = 'L';
            i -= 2;
        } else {
            if(prv[i] == 0) res[i] = 'L';
            else res[i] = 'R';
            i--;
        }
    }
    return true;
}
void test() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    for(int i = 1; i <= m; i++) {
        cin >> f[i];
    }
    int l = -1, r = inf + 1, ans = -1;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            r = mid;
            ans = mid;
        } else {
            l = mid;
        }
    }
    if(ans == -1) {
        cout << ans << '\n';
        return;
    }
    check(ans);
    cout << ans << '\n';
    for(int i = 1; i <= n; i++) {
        cout << res[i];
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--) {
        test();
    }
}      

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