Submission #1212403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212403		yanb	Sprinklers (CEOI24_sprinklers)	C++20	0 / 100	20 ms	3516 KiB

Main

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

struct Event {
    int x, id;
    bool t;

    Event(int x, bool t, int id) : x(x), t(t), id(id) {}

    bool operator<(const Event &o) const {
        if (x == o.x && t < o.t) return id < o.id;
        if (x == o.x) return t < o.t;
        return x < o.x;
    }
};

int n, m;
vector<Event> e;
string ans;

bool check(int x) {
    int lf = -1, rw = -1;
    for (Event c : e) {
        if (c.t) {
            if (lf == -1) {
                rw = c.x + x;
                ans[c.id] = 'R';
            } else {
                if (c.x - lf > x) return 0;
                lf = -1;
                rw = c.x;
                ans[c.id] = 'L';
            }
        } else {
            if (c.x > rw) lf = c.x;
        }
    }
    return lf == -1;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        e.emplace_back(x, 1, i);
    }
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        e.emplace_back(x, 0, i);
    }

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

    sort(e.begin(), e.end());

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