Submission #1208869

#TimeUsernameProblemLanguageResultExecution timeMemory
1208869HappyCapybaraSprinklers (CEOI24_sprinklers)C++20
3 / 100
275 ms10056 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...