Submission #1231979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231979		AlperenT_	Sprinklers (CEOI24_sprinklers)	C++20	0 / 100	187 ms	2040 KiB

Main

#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#define pb push_back
#define F first
#define pii pair<ll,ll> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const int maxn = 1e6  + 10, inf = 1e9+ 10 , mod = 1e9 + 9 ;
int s[maxn] , t[maxn] , dp[maxn] , par[maxn];
char ans[maxn] ;
int n , m;
int find(int x){
    int l = 0, r = m+1 ;
    while(r-l>1){
        int mid = (l+r)/2 ;
        if(t[mid] >= x)r = mid ;
        else l = mid ;
    }
    return r ;
}

bool ch(int k ){
    rep(i ,1 , n){
        dp[i] = dp[i-1] ;
        par[i] = 0  ;
        int id =t[dp[i-1]+1]; 
        if(id <= s[i]){
            if(abs(id-s[i]) <= k){
                dp[i] = find(s[i]+1) - 1 ;
                par[i] = 1; 
            }
        }else{
            if(dp[i] < find(s[i]+k+1)-1){ dp[i] = find(s[i]+k+1) - 1 ; par[i] = 2; }  
        }
        if(i > 1){
            id = t[dp[i-2]+1]; 
            if(id <= s[i] && s[i]-id <= k){
                dp[i] = max(dp[i] , find(s[i-1] + k + 1) - 1);
                par[i] =3 ;
            }
        }
        if(dp[i] == m)return 1 ;
    }
    return 0 ;
}
signed main(){
    ios_base::sync_with_stdio(0) ; cin.tie(0) ;
    cin >> n >> m ;
    rep(i ,1, n){
        cin >> s[i] ;
    }    
    rep(i ,1 , m){
        cin >> t[i] ;
    }
    int l =-1 , r = inf ; 
    while(r-l>1){
        int mid = (l+r)/2 ;
        if(ch(mid) == 1)r =mid ;
        else l = mid ;
    }
    if(r == inf){
        cout << "-1\n";
    }else{
        cout << r << "\n"; 
        int x = n;
        while(x){
            if(par[x] <= 2){
                if(par[x] <= 1){
                    ans[x] = 'L';
                }else{
                    ans[x] = 'R' ;
                }
                x--;
            }else{
                ans[x-1] = 'R' ;
                ans[x] = 'L' ;
                x-=2 ;
            }
        }
        rep(i ,1, n)cout << ans[i] ;
        cout << "\n";
    }

}
/*
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47