oj.uz

Submission #1109662

# Submission time Handle Problem Language Result Execution time Memory
1109662 2024-11-07T09:05:32 Z Pioneer Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 2000 ms 11268 KB 
#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('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 5 ms 6736 KB Correct
2 Correct 6 ms 6736 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6736 KB Correct
2 Correct 12 ms 8140 KB Correct
3 Correct 6 ms 6736 KB Correct
4 Correct 14 ms 8396 KB Correct
5 Correct 14 ms 8396 KB Correct
6 Correct 5 ms 6736 KB Correct
7 Correct 5 ms 6736 KB Correct
8 Correct 7 ms 7124 KB Correct
9 Correct 6 ms 6904 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6736 KB Correct
2 Correct 47 ms 8396 KB Correct
3 Correct 136 ms 6992 KB Correct
4 Correct 1641 ms 11144 KB Correct
5 Correct 1734 ms 11204 KB Correct
6 Correct 5 ms 6736 KB Correct
7 Correct 6 ms 6736 KB Correct
8 Correct 1014 ms 11156 KB Correct
9 Correct 1050 ms 11268 KB Correct
10 Correct 1398 ms 11160 KB Correct
11 Correct 628 ms 8776 KB Correct
12 Correct 713 ms 9796 KB Correct
13 Correct 1492 ms 9768 KB Correct
14 Correct 1553 ms 9924 KB Correct
15 Correct 1771 ms 10100 KB Correct
16 Correct 1370 ms 9676 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6736 KB Correct
2 Correct 6 ms 6736 KB Correct
3 Incorrect 6 ms 6736 KB User solution is incorrect
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6736 KB Correct
2 Correct 317 ms 8508 KB Correct
3 Execution timed out 2052 ms 10956 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6736 KB Correct
2 Correct 6 ms 6736 KB Correct
3 Correct 12 ms 8140 KB Correct
4 Correct 6 ms 6736 KB Correct
5 Correct 14 ms 8396 KB Correct
6 Correct 14 ms 8396 KB Correct
7 Correct 5 ms 6736 KB Correct
8 Correct 5 ms 6736 KB Correct
9 Correct 7 ms 7124 KB Correct
10 Correct 6 ms 6904 KB Correct
11 Correct 47 ms 8396 KB Correct
12 Correct 136 ms 6992 KB Correct
13 Correct 1641 ms 11144 KB Correct
14 Correct 1734 ms 11204 KB Correct
15 Correct 5 ms 6736 KB Correct
16 Correct 6 ms 6736 KB Correct
17 Correct 1014 ms 11156 KB Correct
18 Correct 1050 ms 11268 KB Correct
19 Correct 1398 ms 11160 KB Correct
20 Correct 628 ms 8776 KB Correct
21 Correct 713 ms 9796 KB Correct
22 Correct 1492 ms 9768 KB Correct
23 Correct 1553 ms 9924 KB Correct
24 Correct 1771 ms 10100 KB Correct
25 Correct 1370 ms 9676 KB Correct
26 Incorrect 6 ms 6736 KB User solution is incorrect
27 Halted 0 ms 0 KB -