Submission #1199953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199953		user736482	Sprinklers (CEOI24_sprinklers)	C++20	Compilation error	0 ms	0 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll n,m,a;
vector<ll>v1,v2;
ll dp[100007][2];
ll pop[100007][2];
bool last;//1 to prawo

bool czy(ll x){
    ll ak=0;
    for(ll i=0;i<n;i++){
        vector<ll>v;
        for(;ak<v2.size() && v2[ak]<v1[i];ak++){
            v.pb(v2[ak]);
        }
        v.pb(INFL);
        if(!i){
            dp[0][0]=0;
            if(v[0]+x<v1[i])dp[0][0]=-INFL;
            dp[0][1]=max(v1[i]-v[0],0LL);
        }
        else{
            dp[i][0]=-INFL;
            dp[i][1]=INFL;
            pop[i][0]=1;
            pop[i][1]=0;
            if(dp[i-1][1]+v1[i]-v1[i-1]<=x || (dp[i-1][1]==0 && *lower_bound(v.begin(),v.end(),v1[i-1]+1+x)+x>=v1[i]))dp[i][0]=max(0LL,max(dp[i][0],x-v1[i]+v1[i-1]));
            if(*lower_bound(v.begin(),v.end(),v1[i-1]+dp[i-1][0]+1)+x>=v1[i] && dp[i-1][0]>=0){dp[i][0]=max(0LL,max(dp[i][0],dp[i-1][0]-v1[i]+v1[i-1]));
                if(dp[i][0]==max(0LL,dp[i-1][0]-v1[i]+v1[i-1]))pop[i][0]=0;            
            }
            dp[i][1]=max(0LL,min(dp[i][1],max((dp[i-1][1]+v1[i]-v1[i-1])*(dp[i-1][1]!=0),v1[i]-*lower_bound(v.begin(),v.end(),v1[i-1]+x+1))));
            if(dp[i-1][0]>=0)dp[i][1]=max(0,min(dp[i][1],v1[i]-*lower_bound(v.begin(),v.end(),v1[i-1]+dp[i-1][0]+1)));
            if(dp[i][1]==max(0LL,max((dp[i-1][1]+v1[i]-v1[i-1])*(dp[i-1][1]!=0),v1[i]-*lower_bound(v.begin(),v.end(),v1[i-1]+x+1))))pop[i][1]=1;
            
        }
    }
    if(max(0LL,v2.back()-v1.back())-dp[n-1][0]<=0){
        last=0;
        return 1;
    }
    if(v2.back()-v1.back()<=x && dp[n-1][1]==0){
        last=1;
        return 1;
    }
    return 0;
    
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(ll i=0;i<n;i++){
        cin>>a;
        v1.pb(a);
    }
    for(ll i=0;i<m;i++){
        cin>>a;
        if(*lower_bound(v1.begin(),v1.end(),a)==a)continue;
        v2.pb(a);
    }
    ll pocz=0;
    ll kon=INFL/5;
    while(pocz!=kon){
        ll mid=(pocz+kon)/2;
        if(czy(mid))kon=mid;
        else pocz=mid+1;
    }
    if(kon==INFL/5){
        cout<<-1;return 0;
    }
    cout<<kon<<"\n";
    czy(kon);
    string s;
    for(ll i=0;i<n;i++){
        if(i%3)s.pb('R');
        else s.pb('L');
        last=pop[n-i-1][last];
    }
    reverse(s.begin(),s.end());cout<<s;
}

Compilation message (stderr)

Main.cpp: In function 'bool czy(long long int)':
Main.cpp:42:42: error: no matching function for call to 'max(int, const long long int&)'
   42 |             if(dp[i-1][0]>=0)dp[i][1]=max(0,min(dp[i][1],v1[i]-*lower_bound(v.begin(),v.end(),v1[i-1]+dp[i-1][0]+1)));
      |                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from Main.cpp:2:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
Main.cpp:42:42: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   42 |             if(dp[i-1][0]>=0)dp[i][1]=max(0,min(dp[i][1],v1[i]-*lower_bound(v.begin(),v.end(),v1[i-1]+dp[i-1][0]+1)));
      |                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from Main.cpp:2:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
Main.cpp:42:42: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   42 |             if(dp[i-1][0]>=0)dp[i][1]=max(0,min(dp[i][1],v1[i]-*lower_bound(v.begin(),v.end(),v1[i-1]+dp[i-1][0]+1)));
      |                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from Main.cpp:2:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
Main.cpp:42:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   42 |             if(dp[i-1][0]>=0)dp[i][1]=max(0,min(dp[i][1],v1[i]-*lower_bound(v.begin(),v.end(),v1[i-1]+dp[i-1][0]+1)));
      |                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from Main.cpp:2:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
Main.cpp:42:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   42 |             if(dp[i-1][0]>=0)dp[i][1]=max(0,min(dp[i][1],v1[i]-*lower_bound(v.begin(),v.end(),v1[i-1]+dp[i-1][0]+1)));
      |                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~