Submission #1100727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100727		crafticat	Sprinklers (CEOI24_sprinklers)	C++17	20 / 100	1107 ms	1048576 KiB

Main

#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 (stderr)

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
• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 17 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47