Submission #1140773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140773		Ghulam_Junaid	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	1150 ms	210496 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], a[N];
string used[N];
vector<pair<int, int>> vec;
map<pair<int, int>, bool> store;

map<int, string> output;
bool check(int p, int i){
    if (i == vec.size()) return 1;
    if (store.find({p, i}) != store.end()) return store[{p, i}];

    if (vec[i].S == 0){
        int nxt = i + 1;
        while (nxt < vec.size() and vec[nxt].F <= vec[i].F + p and vec[nxt].S == 1)
            nxt++;
        output[p] += 'R';
        return store[{p, nxt}] = check(p, nxt);
    }

    int last = i;
    while (last < vec.size() and vec[last].S == 1)
        last++;
    if (last == vec.size()) return store[{p, i}] = 0;

    if (vec[last].F - p <= vec[i].F){
        output[p] += 'L';
        if (check(p, last + 1))
            return 1;
        output[p].pop_back();
    }

    int last2 = last;
    while (last2 < vec.size() and vec[last2].S == 1)
        last2++;
    if (last2 == vec.size()) return store[{p, i}] = 0;
    if (vec[last2].F - p > vec[i].F) return store[{p, i}] = 0;

    int nxt = last2 + 1;
    while (nxt < vec.size() and vec[nxt].F <= vec[last].F + p and vec[nxt].S == 1)
        nxt++;
    output[p] += "RL";
    return store[{p, i}] = check(p, nxt);
}

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;
        a[i] = 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, 0)) r = mid;
        else l = mid;
    }

    cout << r << endl;
    cout << output[r] << 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