제출 #1208892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208892		HappyCapybara	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	1318 ms	11212 KiB

Main

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

int n, m;
vector<int> s, f;
set<int> fs;
unordered_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){
    //cout << k << endl;
    string res = "", prev = "";
    for (int i=0; i<n; i++){
        res += 'R';
        prev += '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';
            prev[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';
            prev[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';
            prev[i] = 'L';
            if (i > 1) res[i-2] = prev[i-2];
        }
    }
    if (dp[n] == m-1) return {true, res};
    return {false, res};
}

signed main(){
    cin.tie(0);
    iostream::sync_with_stdio(false);
    cin >> n >> m;
    s.resize(n);
    for (int i=0; i<n; i++) cin >> s[i];
    for (int i=0; i<m; i++){
        int x;
        cin >> x;
        if (i > 0 && x == f.back()) continue;
        f.push_back(x);
        fs.insert(x);
        g[f.back()] = (int)f.size()-1;
    }
    m = f.size();
    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){
        assert(n == 1);
        cout << -1 << endl;
    }
    else cout << r << endl << check(r).second << endl;
}

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