제출 #1153771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153771		byunjaewoo	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	116 ms	4676 KiB

Main

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

const int N=100010, INF=1e9;
int n, m, ans=-1, a[N], b[N], dp[N];
pair<int, int> prv[N];
string ans2, tmp;

bool chk(int x) {
    fill(dp+1, dp+n+2, INF);
    for(int i=1; i<=n+1; i++) prv[i]={0, 0};
    int t=1, s=1;
    tmp.clear();
    for(int i=1; i<=m; i++) tmp+="L";
    dp[1]=1;
    for(int i=1; i<=n; i++) {
        while(dp[i]<=m && b[dp[i]]<a[i]-x) dp[i]++;
        if(dp[i]>m) continue;
        if(b[dp[i]]<=a[i]) {
            int r=upper_bound(a+1, a+n+1, b[dp[i]]+x)-a;
            if(dp[r]>dp[i]+1) dp[r]=dp[i]+1, prv[r]={i, 3};
            continue;
        }
        if(b[dp[i]]<=a[i]+x) {
            int p=upper_bound(a+1, a+n+1, b[dp[i]])-a;
            if(dp[p]>dp[i]+1) dp[p]=dp[i]+1, prv[p]={i, 1};
        }
        if(dp[i]<m && b[dp[i]+1]<=a[i]+x) {
            int q=upper_bound(a+1, a+n+1, b[dp[i]]+x)-a;
            if(dp[q]>dp[i]+2) dp[q]=dp[i]+2, prv[q]={i, 2};
        }
    }
    if(dp[n+1]>m+1) return false;
    for(int i=prv[n+1].first, j=prv[n+1].second; i; j=prv[i].second, i=prv[i].first) {
        if(j==1) tmp[dp[i]-1]='L';
        if(j==2) tmp[dp[i]-1]='R', tmp[dp[i]]='L';
        if(j==3) tmp[dp[i]-1]='R';
    }
    return true;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>m>>n;
    for(int i=1; i<=m; i++) cin>>b[i];
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int s=0, e=INF; s<=e; ) {
        int m=(s+e)/2;
        if(chk(m)) ans2=tmp, ans=m, e=m-1;
        else s=m+1;
    }
    if(ans<0) cout<<-1;
    else cout<<ans<<"\n"<<ans2; 
    return 0;
}

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