Submission #1140763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140763		Ghulam_Junaid	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	180 ms	10724 KiB

Main

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

#define F first
#define S second

const int N = 2e5 + 100;
int dp[N], par[N];
string used[N], output;
vector<pair<int, int>> vec;

int check(int p){
    memset(dp, 0, sizeof dp);
    memset(par, -1, sizeof par);

    for (int i = 0; i < N; i ++) used[i] = "";

    int n = vec.size();
    dp[n] = 1;

    vector<int> inds;
    for (int i = n - 1; i >= 0; i --){
        if (vec[i].S == 0){
            if (inds.size() and vec[inds.back()].F <= vec[i].F + p and dp[inds.back()]){
                dp[i] = 1;
                par[i] = inds.back();
                used[i] = "R";
            }
            else{
                int nxt = lower_bound(vec.begin(), vec.end(), pair<int, int> {vec[i].F + p + 1, -1}) - vec.begin();
                if (dp[nxt]){
                    dp[i] = 1;
                    par[i] = nxt;
                    used[i] = "R";
                }
            }
            inds.push_back(i);
            continue;
        }

        if (inds.empty()){
            dp[i] = 0;
            continue;
        }

        int last = inds.back();
        if (dp[last + 1] and vec[last].F - p <= vec[i].F){
            dp[i] = 1;
            par[i] = last + 1;
            used[i] = "L";
            continue;
        }
        
        if (inds.size() == 1){
            dp[i] = 0;
            continue;
        }

        int last2 = inds[inds.size() - 2];
        int last3 = -1;
        if (inds.size() > 2) last3 = inds[inds.size() - 3];

        if (vec[last2].F - p > vec[i].F) continue;
        int nxt = lower_bound(vec.begin(), vec.end(), pair<int, int> {vec[last].F + p + 1, -1}) - vec.begin();
        if (last3 != -1 and nxt >= last3) nxt = last3;

        if (dp[nxt]){
            dp[i] = 1;
            par[i] = nxt;
            used[i] = "RL";
            continue;
        }
    }

    return dp[0];
}

int main(){
    int n, m;
    cin >> n >> m;

    int X, mn = 1e9, mx = 0;
    for (int i = 0; i < n; i ++){
        int x;
        cin >> x;
        X = x;
        vec.push_back({x, 0});
    }
    for (int i = 0; i < m; i ++){
        int x;
        cin >> x;
        mn = min(mn, x);
        mx = max(mx, x);
        vec.push_back({x, 1});
    }
    sort(vec.begin(), vec.end());

    if (n == 1){
        if (mn < X and X < mx){
            cout << -1 << endl;
        }
        else if (mn < X){
            cout << X - mn << endl;
            cout << "L" << endl;
        }
        else{
            cout << mx - X << endl;
            cout << "R" << endl;
        }
        return 0;
    }

    int l = 0;
    int r = 1e9 + 100;
    while (r - l > 1){
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    check(r);

    cout << r << endl;
    int cur = 0;
    while (cur < vec.size()){
        output += used[cur];
        cur = par[cur];
    }
    cout << output << endl;
}

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