Submission #1212408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212408		yanb	Sprinklers (CEOI24_sprinklers)	C++20	20 / 100	2096 ms	1096 KiB

Main

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

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

bool check(int x) {
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            ans[i] = ((mask & (1 << i)) ? 'R' : 'L');
        }

        vector<bool> ok(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (ans[i] == 'L') {
                    ok[j] = ok[j] || (s[i] - x <= f[j] && f[j] <= s[i]);
                } else {
                    ok[j] = ok[j] || (s[i] <= f[j] && f[j] <= s[i] + x);
                }
            }
        }

        bool aok = 1;
        for (int i = 0; i < m; i++) aok = aok && ok[i];

        if (aok) return 1;
    }
    return 0;
}

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: 0 / 6
• Subtask 3: 17 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47