Submission #1208862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208862		HappyCapybara	Sprinklers (CEOI24_sprinklers)	C++20	3 / 100	333 ms	10056 KiB

Main

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

int n, m;
vector<int> s, f;
set<int> fs;
map<int,int> g;

int gt(int x){
    auto it = fs.lower_bound(x);
    if (it == fs.end()) return -1;
    return g[*it];
}

int lt(int x){
    auto it = fs.upper_bound(x);
    if (it == fs.begin()) return -1;
    it--;
    return g[*it];
}

pair<bool,string> check(int k){
    string res = "";
    for (int i=0; i<n; i++) res += 'R';
    vector<int> dp(n+1, -1);
    for (int i=0; i<n; i++){
        dp[i+1] = dp[i];
        //try left
        int l = gt(s[i]-k), r = lt(s[i]);
        if (l != -1 && l <= r && dp[i] >= l-1 && dp[i+1] < r){
            dp[i+1] = r;
            res[i] = 'L';
        }
        //try right
        l = gt(s[i]), r = lt(s[i]+k);
        if (l != -1 && l <= r && dp[i] >= l-1 && dp[i+1] < r){
            dp[i+1] = r;
            res[i] = 'R';
        }
        if (i == 0) continue;
        //try right left
        if (s[i]-s[i-1] > k) continue;
        l = gt(s[i]-k), r = lt(s[i-1]+k);
        if (l != -1 && l <= r && dp[i-1] >= l-1 && dp[i+1] < r){
            dp[i+1] = r;
            res[i-1] = 'R';
            res[i] = 'L';
        }
    }
    if (dp[n] == m-1) return {true, res};
    return {false, res};
}

signed main(){
    cin >> n >> m;
    s.resize(n);
    f.resize(m);
    for (int i=0; i<n; i++) cin >> s[i];
    for (int i=0; i<m; i++){
        cin >> f[i];
        fs.insert(f[i]);
        g[f[i]] = i;
    }
    int l = -1, r = pow(10, 9)+1;
    while (l < r-1){
        //cout << l << " " << r << endl;
        int mid = (l+r)/2;
        if (check(mid).first) r = mid;
        else l = mid;
    }
    if (r == pow(10, 9)+1) cout << -1 << endl;
    else cout << r << endl << check(r).second << endl;
}

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