oj.uz

Submission #1109668

# Submission time Handle Problem Language Result Execution time Memory
1109668 2024-11-07T09:17:35 Z Pioneer Sprinklers (CEOI24_sprinklers) C++17
26 / 100
 2000 ms 6680 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));
    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=1e9,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;
        }
        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 Correct 4 ms 3596 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3596 KB Correct
2 Correct 9 ms 4264 KB Correct
3 Correct 3 ms 3408 KB Correct
4 Correct 12 ms 5072 KB Correct
5 Correct 12 ms 5072 KB Correct
6 Correct 4 ms 3548 KB Correct
7 Correct 4 ms 3576 KB Correct
8 Correct 5 ms 3664 KB Correct
9 Correct 4 ms 3480 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3408 KB Correct
2 Correct 41 ms 4280 KB Correct
3 Correct 132 ms 3664 KB Correct
4 Correct 1620 ms 6140 KB Correct
5 Correct 1697 ms 6680 KB Correct
6 Correct 4 ms 3408 KB Correct
7 Correct 5 ms 3544 KB Correct
8 Correct 954 ms 6176 KB Correct
9 Correct 916 ms 6164 KB Correct
10 Correct 1266 ms 6172 KB Correct
11 Correct 608 ms 4936 KB Correct
12 Correct 658 ms 5328 KB Correct
13 Correct 1294 ms 5144 KB Correct
14 Correct 1445 ms 5908 KB Correct
15 Correct 1642 ms 5660 KB Correct
16 Correct 1293 ms 5400 KB Correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3408 KB Correct
2 Correct 4 ms 3596 KB Correct
3 Correct 4 ms 3408 KB Correct
4 Correct 5 ms 3408 KB Correct
5 Correct 5 ms 3408 KB Correct
6 Correct 5 ms 3408 KB Correct
7 Correct 5 ms 3408 KB Correct
8 Correct 5 ms 3408 KB Correct
9 Correct 4 ms 3424 KB Correct
10 Correct 5 ms 3408 KB Correct
11 Correct 4 ms 3408 KB Correct
12 Correct 4 ms 3548 KB Correct
13 Correct 5 ms 3408 KB Correct
14 Correct 4 ms 3408 KB Correct
15 Correct 5 ms 3408 KB Correct
16 Correct 5 ms 3408 KB Correct
17 Correct 6 ms 3540 KB Correct
18 Correct 4 ms 3408 KB Correct
19 Correct 6 ms 3408 KB Correct
20 Correct 4 ms 3408 KB Correct

Subtask #4
0.0 / 27.0

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

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3408 KB Correct
2 Correct 4 ms 3596 KB Correct
3 Correct 9 ms 4264 KB Correct
4 Correct 3 ms 3408 KB Correct
5 Correct 12 ms 5072 KB Correct
6 Correct 12 ms 5072 KB Correct
7 Correct 4 ms 3548 KB Correct
8 Correct 4 ms 3576 KB Correct
9 Correct 5 ms 3664 KB Correct
10 Correct 4 ms 3480 KB Correct
11 Correct 41 ms 4280 KB Correct
12 Correct 132 ms 3664 KB Correct
13 Correct 1620 ms 6140 KB Correct
14 Correct 1697 ms 6680 KB Correct
15 Correct 4 ms 3408 KB Correct
16 Correct 5 ms 3544 KB Correct
17 Correct 954 ms 6176 KB Correct
18 Correct 916 ms 6164 KB Correct
19 Correct 1266 ms 6172 KB Correct
20 Correct 608 ms 4936 KB Correct
21 Correct 658 ms 5328 KB Correct
22 Correct 1294 ms 5144 KB Correct
23 Correct 1445 ms 5908 KB Correct
24 Correct 1642 ms 5660 KB Correct
25 Correct 1293 ms 5400 KB Correct
26 Correct 4 ms 3408 KB Correct
27 Correct 5 ms 3408 KB Correct
28 Correct 5 ms 3408 KB Correct
29 Correct 5 ms 3408 KB Correct
30 Correct 5 ms 3408 KB Correct
31 Correct 5 ms 3408 KB Correct
32 Correct 4 ms 3424 KB Correct
33 Correct 5 ms 3408 KB Correct
34 Correct 4 ms 3408 KB Correct
35 Correct 4 ms 3548 KB Correct
36 Correct 5 ms 3408 KB Correct
37 Correct 4 ms 3408 KB Correct
38 Correct 5 ms 3408 KB Correct
39 Correct 5 ms 3408 KB Correct
40 Correct 6 ms 3540 KB Correct
41 Correct 4 ms 3408 KB Correct
42 Correct 6 ms 3408 KB Correct
43 Correct 4 ms 3408 KB Correct
44 Correct 306 ms 4304 KB Correct
45 Execution timed out 2052 ms 6168 KB Time limit exceeded
46 Halted 0 ms 0 KB -