제출 #1140652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140652		Ghulam_Junaid	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	135 ms	11520 KiB

Main

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

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

void work(int p){
    memset(dp, 0, sizeof dp);

    dp[vec.size()] = 1;
    vector<int> si;
    for (int i = vec.size() - 1; i >= 0; i --){
        if (vec[i].second == 1){
            if (si.empty()) dp[i] = 0;
            else{
                int last = si.back();
                if (dp[last + 1] and ((vec[last].first - p) <= vec[i].first)){
                    dp[i] = 1;
                    par[i] = last + 1;
                    used[i] = "L";
                }

                if (si.size() > 1){
                    int last2 = si[si.size() - 2];
                    bool good = ((vec[last2].first - p) <= vec[i].first);
                    
                    if (si.size() > 2 and vec[si[si.size() - 3]].first <= vec[last].first + p){
                        if (good and dp[si[si.size() - 3]]){
                            dp[i] = 1;
                            par[i] = si[si.size() - 3];
                            used[i] = "RL";
                        }
                    }
                    else{
                        int nxt = upper_bound(vec.begin(), vec.end(), (pair<int, int>) {vec[last].first + p, 2}) - vec.begin();
                        if (good and dp[nxt]){
                            dp[i] = 1;
                            par[i] = nxt;
                            used[i] = "RL";
                        }
                    }

                }
            }
        }
        else{
            if (si.size() and vec[si.back()].first <= vec[i].first + p){
                if (dp[si.back()]){
                    dp[i] = 1;
                    par[i] = si.back();
                    used[i] = "R";
                }
            }
            else{
                int nxt = upper_bound(vec.begin(), vec.end(), (pair<int, int>) {vec[i].first + p, 2}) - vec.begin();
                if (dp[nxt]){
                    dp[i] = 1;
                    par[i] = nxt;
                    used[i] = "R";
                }
            }
            si.push_back(i);
        }
    }
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++){
        cin >> a[i];
        vec.push_back({a[i], 0});
    }
    for (int i = 0; i < m; i ++){
        cin >> f[i];
        vec.push_back({f[i], 1});
    }
    sort(vec.begin(), vec.end());

    if (n == 1){
        int mn = f[0];
        int mx = f[m - 1];
        if (mn < a[0] and a[0] < mx)
            cout << -1 << endl;
        else{
            if (mx <= a[0]){
                cout << a[0] - mn << endl;
                cout << "L" << endl;
            }
            else{
                cout << mx - a[0] << endl;
                cout << "R" << endl;
            }
        }
        return 0;
    }

    int l = -1;
    int r = 1e9;
    while (r - l > 1){
        int p = (l + r) / 2;
        work(p);
        
        if (dp[0]) r = p;
        else l = p;
    }

    work(r);
    cout << r << endl;
    int cur = 0;
    while (cur < vec.size()){
        cout << used[cur];
        cur = par[cur];
    }
    cout << 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