oj.uz

Submission #1100727

# Submission time Handle Problem Language Result Execution time Memory
1100727 2024-10-14T14:07:44 Z crafticat Sprinklers (CEOI24_sprinklers) C++17
20 / 100
 1107 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n, m;
    cin>>n>>m;
    vector<ll> spri(n);
    vector<ll> flow(m);
    for(ll e=0; e<n; e++) cin>>spri[e];
    for(ll r=0; r<m; r++) cin>>flow[r];
    //first check if it is possible (not done!!)
    if(n==1){
        if(flow[0]<spri[0] and flow[m-1]>spri[0]){
            cout<<-1;
            return 0;
        }
        else{
            if(spri[0]>=flow[m-1]){
                cout<<spri[0]-flow[0]<<"\n";
                cout<<"L";
            }
            else{
                cout<<flow[m-1]-spri[0]<<"\n";
                cout<<"R";
            }
            return 0;
        }
    }
    //binary search using dp here, O((n+m)log(10^9);
    set<int> flowers;
    for(int i=0; i<m; i++){
        flowers.insert(flow[i]);
    }
    int a=-1, b=1000000000;
    vector<int> dp(n+1, -1);
    dp[0]=-1;
    vector<string> dps(n+1, "");
    dps[0]="";
    while(a<b-1){
        int c=(a+b+1)/2;
        bool works=1;
        if(flow[0]+c<spri[0]) works=0;
        if(flow[0]<spri[0]){ 
            dp[1]=spri[0];
        }
        else{ 
            dp[1]=spri[0]+c;
        }
        for(int i=2; i<=n; i++){
            if(flowers.upper_bound(dp[i-1])==flowers.end()){
                dp[i]=dp[i-1];
            }
            else{
                int d = *flowers.upper_bound(dp[i-1]);
                if(d>=spri[i-1]){
                    dp[i]=spri[i-1]+c;
                }
                else{
                    int e=*flowers.upper_bound(dp[i-2]);
                    if(d+c<spri[i-1]){
                        works=0;
                        i=n+1;
                        continue;
                    }
                    if(e+c>=spri[i-1]){
                        if(spri[i-2]+c>=spri[i-1]){
                            dp[i]=spri[i-2]+c;
                        }
                        else{
                            dp[i]=spri[i-1];
                        }
                    }
                    else{
                        dp[i]=spri[i-1];
                    }
                }
            }
        }
        if(dp[n]<flow[m-1]) works=0;
        if (works) b=c;
        else a=c;
    }
    cout<<b<<"\n";
    int c=b;
        bool works=1;
        if(flow[0]+c<spri[0]) works=0;
        if(flow[0]<spri[0]){ 
            dp[1]=spri[0];
            dps[1]="L";
        }
        else{ 
            dp[1]=spri[0]+c;
            dps[1]="R";
        }
        for(int i=2; i<=n; i++){
            if(flowers.upper_bound(dp[i-1])==flowers.end()){
                dp[i]=dp[i-1];
                dps[i]=dps[i-1]+"L";
            }
            else{
                int d = *flowers.upper_bound(dp[i-1]);
                if(d>=spri[i-1]){
                    dp[i]=spri[i-1]+c;
                    dps[i]=dps[i-1]+"R";
                }
                else{
                    int e=*flowers.upper_bound(dp[i-2]);
                    if(d+c<spri[i-1]){
                        works=0;
                        i=n+1;
                        continue;
                    }
                    if(e+c>=spri[i-1]){
                        if(spri[i-2]+c>=spri[i-1]){
                            dp[i]=spri[i-2]+c;
                            dps[i]=dps[i-2]+"RL";
                        }
                        else{
                            dp[i]=spri[i-1];
                            dps[i]=dps[i-2]+"RL";
                        }
                    }
                    else{
                        dp[i]=spri[i-1];
                        dps[i]=dps[i-1]+"L";
                    }
                }
            }
        }
    cout<<dps[n];
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:86:14: warning: variable 'works' set but not used [-Wunused-but-set-variable]
   86 |         bool works=1;
      |              ^~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 0 ms 336 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Correct
2 Correct 20 ms 1352 KB Correct
3 Correct 1 ms 336 KB Correct
4 Correct 24 ms 2036 KB Correct
5 Correct 24 ms 2140 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 5 ms 700 KB Correct
9 Correct 1 ms 336 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 42 ms 5380 KB Correct
3 Correct 65 ms 84308 KB Correct
4 Runtime error 907 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 0 ms 336 KB Correct
3 Correct 1 ms 336 KB Correct
4 Correct 1 ms 336 KB Correct
5 Correct 1 ms 336 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 1 ms 336 KB Correct
9 Correct 1 ms 504 KB Correct
10 Correct 1 ms 336 KB Correct
11 Correct 1 ms 440 KB Correct
12 Correct 1 ms 340 KB Correct
13 Correct 1 ms 340 KB Correct
14 Correct 1 ms 436 KB Correct
15 Correct 1 ms 508 KB Correct
16 Correct 1 ms 340 KB Correct
17 Correct 1 ms 340 KB Correct
18 Correct 1 ms 340 KB Correct
19 Correct 1 ms 340 KB Correct
20 Correct 1 ms 340 KB Correct

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 151 ms 88668 KB Correct
3 Runtime error 1107 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 0 ms 336 KB Correct
3 Correct 20 ms 1352 KB Correct
4 Correct 1 ms 336 KB Correct
5 Correct 24 ms 2036 KB Correct
6 Correct 24 ms 2140 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 1 ms 336 KB Correct
9 Correct 5 ms 700 KB Correct
10 Correct 1 ms 336 KB Correct
11 Correct 42 ms 5380 KB Correct
12 Correct 65 ms 84308 KB Correct
13 Runtime error 907 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -