Submission #1109663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109663		Pioneer	Sprinklers (CEOI24_sprinklers)	C++17	3 / 100	309 ms	9164 KiB

Main

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

#define ll long long
#define int ll
#define all(v) v.begin(),v.end()
#define sz(s) ((int)s.size())
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound

using namespace std;

const ll inf=1e18;
const int MAX=1e5+10;
const int MX=1e8;
const int mod=1e9+7;

int binpow(int a,int n){
    if(!n)return 1;
    if(n%2==1)return a*binpow(a,n-1)%mod;
    int k=binpow(a,n/2);
    return k*k%mod;
}

int n,m;
int s[MAX],f[MAX];
int dp[MAX][4];
int pr[MAX][4];
vector<int> vf;

bool check(int mid){
    memset(dp,-1,sizeof(dp));
    memset(pr,-1,sizeof(pr));
    // if(f[1]>=s[1])dp[1][0]=s[1]+k;
    // if(f[1]>=s[1]-k)dp[1][3]=s[1];
    // {
    //     if(s[2]-s[1]<=k){
    //         bool ok=1;
    //         for(int i=1;i<=m;i++){
    //             if(f[i]<=s[2]){
    //                 if(!((s[2]-k<=f[i]&&f[i]<=s[2])||(s[1]<=f[i]&&f[i]<=s[1]+k)))ok=0;
    //             }
    //         }
    //         if(ok)dp[2][1]=max(s[2],s[1]+k);
    //     }
    // }
    // {
    //     bool ok=1;
    //     for(int i=1;i<=m;i++){
    //         if(f[i]<=s[2]){
    //             if(!((s[2]-k<=f[i]&&f[i]<=s[2])||(s[1]-k<=f[i]&&f[i]<=s[1])))ok=0;
    //         }
    //     }
    //     if(ok)dp[2][2]=s[2];
    // }
    // {
    //     bool ok=1;
    //     for(int i=1;i<=m;i++){
    //         if(f[i]<=s[2]){
    //             if(!(s[1]<=f[i]&&f[i]<=s[1]+k||s[2]==f[i]))ok=0;
    //         }
    //     }
    //     if(ok)dp[2][0]=s[2]+k,pr[2][0]=0;
    // }
    // cout<<dp[1][0]<<" "<<dp[1][1]<<" "<<dp[1][2]<<" "<<dp[1][3]<<"\n";
    // cout<<dp[2][0]<<" "<<dp[2][1]<<" "<<dp[2][2]<<"\n";
    for(int i=1;i<=n;i++){
        for(int j=0;j<4;j++){
            int k=i-1;
            if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i]){
                if(max(dp[k][j],s[i]+mid)>dp[i][0]){
                    pr[i][0]=j;
                    dp[i][0]=max(dp[k][j],s[i]+mid);
                }
            }
            if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i]-mid){
                if(max(dp[k][j],s[i])>dp[i][3]){
                    pr[i][3]=j;
                    dp[i][3]=max(dp[k][j],s[i]);
                }
            }
            k--;
            if(k<0)continue;
            if(s[i]-s[i-1]>mid){
                if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i-1]){
                    if(ub(all(vf),max(dp[k][j],s[i-1]+mid))==vf.end()||vf[ub(all(vf),max(dp[k][j],s[i-1]+mid))-vf.begin()]>=s[i]-mid){
                        if(max(dp[k][j],s[i])>dp[i][1]){
                            pr[i][1]=j;
                            dp[i][1]=max(dp[k][j],s[i]);
                        }            
                    } 
                }
            }
            else{
                if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i]-mid){
                    if(max(dp[k][j],s[i-1]+mid)>dp[i][1]){
                        pr[i][1]=j;
                        dp[i][1]=max(dp[k][j],s[i-1]+mid);
                    }
                }
            }
            if(s[i]-s[i-1]>mid){
                if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i-1]-mid){
                    if(ub(all(vf),max(dp[k][j],s[i-1]))==vf.end()||vf[ub(all(vf),max(dp[k][j],s[i-1]))-vf.begin()]>=s[i]-mid){
                        if(max(dp[k][j],s[i])>dp[i][1]){
                            pr[i][2]=j;
                            dp[i][2]=max(dp[k][j],s[i]);
                        }            
                    } 
                }
            }
            else{
                if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i-1]-mid){
                    if(max(dp[k][j],s[i-1]+mid)>dp[i][1]){
                        pr[i][2]=j;
                        dp[i][2]=max(dp[k][j],s[i]);
                    }
                }
            }
        }
        // for(int j=0;j<4;j++){
        //     if(dp[i][j]!=-1)cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
        // }
    }
    for(int j=0;j<4;j++){
        // cout<<dp[n][j]<<"\n";
        if(dp[n][j]>=f[m])return 1;
    }
    return 0;
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<=m;i++){
        cin>>f[i];
        vf.pb(f[i]);
    }
    int l=0,r=2e9,res=-1;
    while(l<=r){
        int m=(l+r)/2;
        if(check(m)){
            r=m-1;
            res=m;
        }
        else l=m+1;
    }
    cout<<res<<"\n";
    if(res!=-1){
        check(res);
        int a=n,b=-1;
        string s;
        for(int k=0;k<3;k++)if(dp[n][k]>=f[n])b=k;
        while(a>0){
            if(b==0){
                b=pr[a][b];
                a--;
                s.pb('R');
            }
            else if(b==1){
                b=pr[a][b];
                a-=2;
                s.pb('R');
                s.pb('L');
            }
            else if(b==2){
                b=pr[a][b];
                a-=2;
                s.pb('L');
                s.pb('L');
            }
            else{
                b=pr[a][b];
                a--;
                s.pb('L');
            }
        }
        reverse(all(s));
        cout<<s<<"\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
}

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