Submission #1363959

#TimeUsernameProblemLanguageResultExecution timeMemory
1363959madamadam3Sprinklers (CEOI24_sprinklers)C++20
3 / 100
2095 ms3544 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long int

const int INF = 4e18;
template<class T> bool chmax(T& a, const T& b) {return a < b ? a = b, 1 : 0;}
template<class T> bool chmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpi = vector<pi>;
using vvpi = vector<vector<pi>>;

#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int)((x).size())
#define rep(i,a,b) for (int i = a; i < b; i++)
#define rev(i,a,b) for (int i = a; i >= b; i--)

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int n,m; cin >> n >> m;
    vi s(n); for (auto &x : s) cin >> x;
    vi f(m+1, -INF); rep(i, 1, m+1) cin >> f[i];

    if (n == 1 && f[1] < s[0] && f[m] > s[0]) {
        cout << "-1\n";
        return 0;
    }

    vi nearest(n);
    int pos = 0;
    rep(i, 0, n) {
        while (pos < m && f[pos+1] < s[i]) pos++;
        nearest[i] = f[pos];
    }

    auto build = [&](int x) {
        vi orient(n);
        if (f[1] >= s[0]) orient[0] = 1;

        rep(i, 1, n) {
            if (orient[i-1] == 0 && nearest[i] > s[i-1]) orient[i] = 0;
            else if (orient[i-1] == 0 && nearest[i] <= s[i-1]) orient[i] = 1;
            else if (orient[i-1] == 1 && nearest[i] > s[i-1]+x) orient[i] = 0;
            else orient[i] = 1;
        }
        return orient;
    };

    auto check = [&](int x) {
        vi orient = build(x);

        bool ok = true;
        rep(i, 1, m+1) {
            bool found = false;
            rep(j, 0, n) {
                found = found || (orient[j] == 0 && s[j] >= f[i] && f[i]+x >= s[j]) || (orient[j] == 1 && s[j] <= f[i] && s[j]+x >= f[i]);
            }
            ok = ok && found;
        }
        return ok;
    };

    int lo = 0, hi = 2e9;
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (check(mid)) hi = mid;
        else lo = mid + 1;
    }

    cout << lo << "\n";
    auto o = build(lo);
    rep(i, 0, n) cout << (o[i] == 0 ? "L" : "R"); cout << "\n";
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...