Submission #1109644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109644		Pioneer	Sprinklers (CEOI24_sprinklers)	C++17	0 / 100	212 ms	8496 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 k){
    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=3;i<=n;i++){
        for(int j=0;j<4;j++){
            int k=i-1;
            if(dp[k][j]!=-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]+k)>dp[i][0]){
                    pr[i][0]=j;
                    dp[i][0]=max(dp[k][j],s[i]+k);
                }
            }
            if(dp[k][j]!=-1){
                if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i]-k){
                    if(max(dp[k][j],s[i]+k)>dp[i][3]){
                        pr[i][3]=j;
                        dp[i][3]=max(dp[k][j],s[i]+k);
                    }
                }
            }
            k--;
            if(dp[k][j]==-1)continue;
            if(s[i]-s[i-1]>k){
                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]+k))==vf.end()||vf[ub(all(vf),max(dp[k][j],s[i-1]+k))-vf.begin()]>=s[i]-k){
                        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]-k){
                    if(max(dp[k][j],s[i-1]+k)>dp[i][1]){
                        pr[i][1]=j;
                        dp[i][1]=max(dp[k][j],s[i-1]+k);
                    }
                }
            }
            if(s[i]-s[i-1]>k){
                if(ub(all(vf),dp[k][j])==vf.end()||vf[ub(all(vf),dp[k][j])-vf.begin()]>=s[i-1]-k){
                    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]-k){
                        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]-k){
                    if(max(dp[k][j],s[i-1]+k)>dp[i][1]){
                        pr[i][2]=j;
                        dp[i][2]=max(dp[k][j],s[i]);
                    }
                }
            }
        }
        // cout<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<"\n";
    }
    for(int j=0;j<4;j++)if(dp[n][j]>=f[n])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]);
    }
    // check(6);
    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('L');
                s.pb('R');
            }
            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();
}

Compilation message (stderr)

Main.cpp: In function 'bool check(long long int)':
Main.cpp:66:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   66 |                 if(!(s[1]<=f[i]&&f[i]<=s[1]+k||s[2]==f[i]))ok=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