제출 #1268273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268273		antonn	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	74 ms	2120 KiB

Main

#include <bits/stdc++.h> 

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 1e5 + 7;

int n, m, a[N], b[N], p[N], dp[N];

bool check(int d) {
    int j = 1, k = 1, l = 1;
    for (int i = 1; i <= n; ++i) {
        if (b[dp[i - 1] + 1] < a[i] - d) return false;
        while (j <= m && b[j] <= a[i] + d) ++j;
        while (k <= m && b[k] <= a[i]) ++k;
        if (i > 1) {
            while (l <= m && b[l] <= a[i - 1] + d) ++l;
        }
        if (b[dp[i - 1] + 1] >= a[i]) {
            dp[i] = j - 1;
            p[i] = 1;
        } else {
            dp[i] = k - 1;
            p[i] = 0;
        }
        
        if (i > 1 && b[dp[i - 2] + 1] >= a[i] - d && dp[i] < l) {
            dp[i] = l - 1;
            p[i] = -1;
        }
    }
    return dp[n] == m;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) cin >> b[i];
    b[m + 1] = 2e9 + 10;
    
    int low = 0, high = 1e9, sol = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            sol = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    check(sol);
    cout << sol << "\n";
    if (sol == -1) return 0;
    
    vector<char> s(n + 1);
    for (int i = n; i >= 1; --i) {
        if (p[i] == -1) {
            s[i] = 'L';
            s[i - 1] = 'R';
            --i;
        } else {
            s[i] = (p[i] == 0 ? 'L' : 'R');
        }
    }
    for (int i = 1; i <= n; ++i) cout << s[i];
}

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