Submission #1109665

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109665	2024-11-07T09:13:36 Z	Pioneer	Sprinklers (CEOI24_sprinklers)	C++17	6 / 100	2000 ms	5580 KB

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));
    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<4;k++)if(dp[n][k]>=f[n]){
            b=k;
            break;
        }
        // cout<<pr[a][b]<<" "<<b<<"\n";
        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();
}

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3408 KB	Correct
2	Execution timed out	2052 ms	3408 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #1
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2052 ms	3408 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3408 KB	Correct
2	Correct	43 ms	4304 KB	Correct
3	Correct	132 ms	3700 KB	Correct
4	Correct	1648 ms	4884 KB	Correct
5	Correct	1710 ms	5064 KB	Correct
6	Correct	4 ms	3408 KB	Correct
7	Correct	4 ms	3508 KB	Correct
8	Correct	960 ms	5064 KB	Correct
9	Correct	969 ms	4888 KB	Correct
10	Correct	1370 ms	5064 KB	Correct
11	Correct	582 ms	4236 KB	Correct
12	Correct	667 ms	4560 KB	Correct
13	Correct	1466 ms	5580 KB	Correct
14	Correct	1464 ms	4628 KB	Correct
15	Correct	1570 ms	4708 KB	Correct
16	Correct	1309 ms	4636 KB	Correct