제출 #1140650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140650		hashimali	Sprinklers (CEOI24_sprinklers)	C++17	100 / 100	1020 ms	4360 KiB

Main

#include <bits/stdc++.h>
#define endl '\n'
#define ld long double
#define pb push_back
#define pf push_front
#define mod 998244353
#define se second
#define fi first
#define all(ls) (ls).begin(),(ls).end()
#define int long long
using namespace std;
int n,m,works;
const int N=1e5+10;
vector<int>s,f;
int par[N],d[N],dp[N];
pair<int,int>nxt(int x){
    return {lower_bound(all(f),x)-f.begin(),upper_bound(all(f),x)-f.begin()-1};
}
void work(int mid){
    works=0;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        pair<int,int>a=nxt(s[i]-mid),b=nxt(s[i]),c=nxt(s[i]+mid);
        dp[i]=dp[i-1];
        par[i]=i-1;
        if((dp[i-1]+1)>=a.fi and dp[i]<b.se){
            d[i]=0;
            dp[i]=b.se;
        }
        if((dp[i-1]+1)>=b.fi and dp[i]<c.se){
            d[i]=1;
            dp[i]=c.se;
        }
        if(i>1){
            pair<int,int>D=nxt(s[i-1]+mid);
            if((dp[i-2]+1)>=a.fi and dp[i]<D.se){
                d[i]=1;
                par[i]=i-2;
                dp[i]=D.se;
            }
        }
    }
    works=(dp[n]==m);
}
void solve(){
    cin>>n>>m;
    s.resize(n+1);
    f.resize(m+1);
    for(int i=1;i<=n;i++)
        cin>>s[i];
    for(int i=1;i<=m;i++)
        cin>>f[i];
    int low=0,high=1e14,f=0;
    while(low<=high){
        int mid=(low+high)/2;
        work(mid);
        if(works){
            f=1;
            high=mid-1;
        }
        else
            low=mid+1;
    }
    if(f==0)
        low=-1;
    cout<<low<<endl;
    if(low!=-1){
        work(low);
        // for(int i=1;i<=n;i++)
        //     cout<<dp[i]<<" ";
        // cout<<endl;
        // for(int i=1;i<=n;i++)
        //     cout<<par[i]<<" ";
        // cout<<endl;
        int i=n;
        while(i>0){
            if(par[i]+2==i){
                d[i]=0;
                d[i-1]=1;
            }
            i=par[i];
        }
        for(int i=1;i<=n;i++){
            if(d[i]==0)
                cout<<'L';
            else
                cout<<'R'; 
        }
        cout<<endl;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    for(int i=1;i<=t;i++){
        // cout<<"Scenario #"<<i<<":"<<" ";
        solve();
    }
}

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