| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1364750 | Aviansh | Sprinklers (CEOI24_sprinklers) | C++20 | 393 ms | 4736 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin >> n >> m;
int s[n+2];
for(int i = 1;i<=n;i++){
cin >> s[i];
}
s[0]=-1e18;
s[n+1]=1e18;
int f[m];
for(int i = 0;i<m;i++){
cin >> f[i];
}
char ans[n];
n++;
n++;
auto check = [&] (int k){
array<bool,3> dp[n];
//{XR,RL,LL}
fill(dp,dp+n,(array<bool,3>){0,0,0});
array<int,3> backtrack[n];
fill(backtrack,backtrack+n,(array<int,3>){-1,-1,-1});
dp[0]={1,1,1};
for(int i = 1;i<n;i++){
int lef = upper_bound(f,f+m,s[i-1])-f;
int rig = lower_bound(f,f+m,s[i])-f-1;
//can i being R include all from lef-rig
if(rig==-1||f[rig]<=s[i-1]+k){
dp[i][0]|=dp[i-1][0];
if(dp[i-1][0]){
backtrack[i][0]=0;
}
}
if(lef>rig){
//no one in between
dp[i][0]|=dp[i-1][0]|dp[i-1][1]|dp[i-1][2];
if(dp[i-1][0]){
backtrack[i][0]=0;
}
if(dp[i-1][1]){
backtrack[i][0]=1;
}
if(dp[i-1][2]){
backtrack[i][0]=2;
}
}
//current R has been check
//RL case
//transition from dp[i-1][0] only.
int reachcur = lower_bound(f,f+m,s[i]-k)-f;
int reachprev = upper_bound(f,f+m,s[i-1]+k)-f-1;
if(reachcur<=reachprev||reachcur==reachprev+1){
//RL is possible
dp[i][1]|=dp[i-1][0];
if(dp[i-1][0]){
backtrack[i][1]=0;
}
}
//LL case
//transition from dp[i-1][1] and [2] SEPERATELY
//[2] first (LLL)
if(reachcur<=lef){
dp[i][2]|=dp[i-1][2];
if(dp[i-1][2]){
backtrack[i][2]=2;
}
}
//[1] now (RLL)
if(reachcur<=lef){
dp[i][2]|=dp[i-1][1];
if(dp[i-1][1]){
backtrack[i][2]=1;
}
}
else{
//it alone cant reach but maybe using 3rd last it can
if(i-2>=0){
//exists
int reach = upper_bound(f,f+m,s[i-2]+k)-f-1;
if(reachcur<=reach||reachcur==reach+1){
//overlapping so can do
dp[i][2]|=dp[i-1][1];
if(dp[i-1][1]){
backtrack[i][2]=1;
}
}
}
}
}
bool x = dp[n-1][0]||dp[n-1][1]||dp[n-1][2];
if(x){
int state = -1;
for(int i = 0;i<3;i++){
if(dp[n-1][i]){
state=i;
}
}
assert(state!=-1);
for(int i = n-1;i>=2;i--){
//go to prevs state
state=backtrack[i][state];
if(state==0){
ans[i-2]='R';
}
else{
ans[i-2]='L';
}
}
}
return x;
};
int lo = 0;
int hi = 2e9;
while(lo<hi){
int mid = (lo+hi)/2;
if(check(mid)){
hi=mid;
}
else{
lo=mid+1;
}
}
if(lo==2e9){
cout << -1;
return 0;
}
check(lo);
cout << lo << "\n";
for(int i = 0;i<n-2;i++){
cout << ans[i];
}
return 0;
}
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
