제출 #1153717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153717		byunjaewoo	Sprinklers (CEOI24_sprinklers)	C++20	0 / 100	70 ms	3652 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+1, INF);
    for(int i=0; i<n; i++) {
        while(dp[i]<=m && b[dp[i]]<a[i+1]) dp[i]++;
        if(dp[i]>m) continue;
        int p=upper_bound(a+1, a+n+1, b[dp[i]])-a-1;
        if(dp[p]>dp[i]+1) dp[p]=dp[i]+1, prv[p]={i, 1};
        if(dp[i]<m) {
            int q=upper_bound(a+1, a+n+1, b[dp[i]+1]+x)-a-1;
            if(dp[q]>dp[i]+2) dp[q]=dp[i]+2, prv[q]={i, 2};
        }
    }
    if(dp[n]>m) return false;
    tmp.clear();
    for(int i=1; i<=m; i++) tmp+="L";
    for(int i=prv[m].first, j=prv[m].second; i>=0; j=prv[i].second, i=prv[i].first) {
        if(j==1) tmp[dp[i]]='L';
        else tmp[dp[i]]='R', tmp[dp[i]+1]='L';
        if(i==0) break;
    }
    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];
    sort(a+1, a+n+1), sort(b+1, b+m+1);
    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: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47