Submission #1232261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232261		alexander707070	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	405 ms	1628 KiB

Main

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

const int inf=2e9+7;

int n,m;
int s[MAXN],t[MAXN];

int ans;
char sol[MAXN];

bool dp[MAXN][4];

int check(int sp,int len,int last){
    int l=0,r=m+1,tt;

    while(l+1<r){
        tt=(l+r)/2;

        if(t[tt]<last){
            l=tt;
        }else{
            r=tt;
        }
    }

    if(l==0 or t[tt]<=s[sp])return 0;

    if(s[sp]+len<t[l])return 3;
    if(s[sp-1]+len<t[l])return 1;
    return 2;
}

bool ok(int len){

    dp[0][0]=true;
    dp[0][1]=dp[0][2]=dp[0][3]=false;

    for(int i=1;i<=n;i++){
        dp[i][3]=false;

        for(int fl=0;fl<3;fl++){

            if(fl==0){
                dp[i][fl]=dp[i-1][check(i-1,len,s[i]-len)];
            }else if(fl==1){
                dp[i][fl]=dp[i-1][check(i-1,len,s[i])];
            }else{
                dp[i][fl]=dp[i-1][check(i-1,len,s[i])];
                if(i>1)dp[i][fl]=(dp[i][fl] or dp[i-2][check(i-2,len,s[i]-len)]);
            }
        }
    }

    int et=check(n,len,inf);
    return dp[n][et];
}

void findsol(int i,int fl,int len){
    if(i==0)return;

    if(fl==0){
        sol[i]='L';
        findsol(i-1,check(i-1,len,s[i]-len),len);
    }else if(fl==1){
        sol[i]='R';
        findsol(i-1,check(i-1,len,s[i]),len);
    }else{
        if(dp[i-1][check(i-1,len,s[i])]){
            sol[i]='R';
            findsol(i-1,check(i-1,len,s[i]),len);
        }else{
            sol[i]='L';
            sol[i-1]='R';
            findsol(i-2,check(i-2,len,s[i]-len),len);
        }
    }
}

int bin(){
    int l=-1,r=inf/2,tt;

    while(l+1<r){
        tt=(l+r)/2;

        if(ok(tt)){
            r=tt;
        }else{
            l=tt;
        }
    }

    return r;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<=m;i++)cin>>t[i];

    ans=bin();

    if(ans==inf/2){
        cout<<"-1\n";
    }else{
        ok(ans);

        int et=check(n,ans,inf);
        findsol(n,et,ans);

        cout<<ans<<"\n";
        for(int i=1;i<=n;i++)cout<<sol[i];
        cout<<"\n";
    }

    return 0;
}

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