Submission #1364719

#TimeUsernameProblemLanguageResultExecution timeMemory
1364719AvianshSprinklers (CEOI24_sprinklers)C++20
6 / 100
353 ms4736 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    int s[n+1];
    for(int i = 0;i<n;i++){
        cin >> s[i];
    }
    s[n]=1e18;
    int f[m];
    for(int i = 0;i<m;i++){
        cin >> f[i];
    }
    char ans[n];
    n++;
    auto check = [&] (int k){
        array<bool,3> dp[n];
        //{XR,RL,LL}
        fill(dp,dp+n,(array<bool,3>){0,0,0});
        array<int,3> backtrack[n];
        fill(backtrack,backtrack+n,(array<int,3>){-1,-1,-1});
        if(s[0]<f[0]){
            dp[0]={1,1,1};
            ans[0]='R';
        }
        else{
            if(s[0]-f[0]<=k){
                dp[0]={0,1,1};
                ans[0]='L';
            }
            else{
                return false;
            }
        }
        for(int i = 1;i<n;i++){
            int lef = upper_bound(f,f+m,s[i-1])-f;
            int rig = upper_bound(f,f+m,s[i])-f-1;
            //can i being R include all from lef-rig
            if(rig==-1||f[rig]<=s[i-1]+k){
                dp[i][0]|=dp[i-1][0];
                if(dp[i-1][0]){
                    backtrack[i][0]=0;
                }
            }
            if(lef>rig){
                //no one in between
                dp[i][0]|=dp[i-1][0]|dp[i-1][1]|dp[i-1][2];
                if(dp[i-1][0]){
                    backtrack[i][0]=0;
                }
                if(dp[i-1][1]){
                    backtrack[i][0]=1;
                }
                if(dp[i-1][2]){
                    backtrack[i][0]=2;
                }
            }
            //current R has been check
            //RL case
            //transition from dp[i-1][0] only.
            int reachcur = lower_bound(f,f+m,s[i]-k)-f;
            int reachprev = upper_bound(f,f+m,s[i-1]+k)-f-1;
            if(reachcur<=reachprev||reachcur==reachprev+1){
                //RL is possible
                dp[i][1]|=dp[i-1][0];
                if(dp[i-1][0]){
                    backtrack[i][1]=0;
                }
            }
            //LL case
            //transition from dp[i-1][1] and [2] SEPERATELY
            //[2] first (LLL)
            if(reachcur<=lef){
                dp[i][2]|=dp[i-1][2];
                if(dp[i-1][2]){
                    backtrack[i][2]=2;
                }
            }
            //[1] now (RLL)
            if(reachcur<=lef){
                dp[i][2]|=dp[i-1][1];
                if(dp[i-1][1]){
                    backtrack[i][2]=1;
                }
            }
            else{
                //it alone cant reach but maybe using 3rd last it can
                if(i-2>=0){
                    //exists
                    int reach = upper_bound(f,f+m,s[i-2]+k)-f-1;
                    if(reachcur<=reach||reachcur==reach+1){
                        //overlapping so can do
                        dp[i][2]|=dp[i-1][1];
                        if(dp[i-1][1]){
                            backtrack[i][2]=1;
                        }
                    }
                }
            }
        }
        bool x = dp[n-1][0]||dp[n-1][1]||dp[n-1][2];
        if(x){
            int state = 0;
            for(int i = n-1;i>=1;i--){
                //go to prevs state
                state=backtrack[i][state];
                if(state==0){
                    ans[i-1]='R';
                }
                else{
                    ans[i-1]='L';
                }
            }
        }
        return x;
    };
    int lo = 0;
    int hi = 2e9;
    while(lo<hi){
        int mid = (lo+hi)/2;
        if(check(mid)){
            hi=mid;
        }
        else{
            lo=mid+1;
        }
    }
    if(lo==2e9){
        cout << -1;
        return 0;
    }
    check(lo);
    cout << lo << "\n";
    for(char c:ans){
        cout << c;
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...