Submission #1167289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167289		juliany2	Sprinklers (CEOI24_sprinklers)	C++20	26 / 100	50 ms	1484 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);
    for (int &i : s)
        cin >> i;
    for (int &i : f)
        cin >> i;

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

        string dir(n, 'L');

        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s[i] <= f[j]) {
                dir[i] = 'R';
                while (j < m && f[j] <= s[i] + mid)
                    j++;
                i++;
            } else {
                int i2 = i - 1;
                while (i2 + 1 < n && s[i2 + 1] <= f[j] + mid)
                    i2++;

                if (i2 == i - 1)
                    break;

                if (i == i2) {
                    dir[i] = 'L';
                    while (j < m && f[j] <= s[i])
                        j++;
                } else if (i + 1 == i2) {
                    int nxt = upper_bound(all(f), s[i]) - f.begin();
                    if (nxt < m && f[nxt] < s[i2]) {
                        dir[i] = 'R';
                        dir[i2] = 'L';

                        while (j < m && f[j] <= s[i] + mid)
                            j++;
                    } else {
                        dir[i] = 'L';
                        dir[i2] = 'R';

                        while (j < m && f[j] <= s[i2] + mid)
                            j++;
                    }
                } else {
                    dir[i] = dir[i2] = 'R';

                    while (j < m && f[j] <= s[i2] + mid)
                        j++;
                }

                i = i2 + 1;
            }
        }

        if (j == m)
            o = dir, ans = mid, hi = mid - 1;
        else
            lo = mid + 1;
    }

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

    return 0;
}

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