#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int inf = 1e15;
const int N = 1e5+5;
int32_t main(){
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
int n, m;
cin>>n>>m;
vector<int> s(n), f(m);
for(int i = 0; i < n; i++){
cin>>s[i];
}
for(int i = 0; i < m; i++){
cin>>f[i];
}
int l = 0, r = mod;
while(l < r){
int mid = (l + r)/2;
vector<int> right(n), us(n);
int ind = 0;
for(int i = 0; i < n; i++){
while(ind < m && s[i] + mid >= f[ind]) ind++;
right[i] = ind; // sağı sulayarak alabileceğim son çiçek + 1
}
ind = 0;
for(int i = 0; i < n; i++){
while(ind < m && s[i] >= f[ind]) ind++;
us[i] = ind; // benden büyük ilk çiçek
}
vector<int> dp(n+1); // dp[i] => ilk i tane sprinkle ile maximum alınabilecek flower prefixi
for(int i = 0; i < n; i++){
dp[i+1] = max(dp[i+1], dp[i]);
if(dp[i] == m) continue;
int j = dp[i];
if(f[j] <= s[i] && s[i] - mid <= f[j]){ // sola
dp[i+1] = max(dp[i+1], us[i]);
}
if(f[j] >= s[i] && s[i] + mid <= f[j]){
dp[i+1] = max(dp[i+1], right[i]);
}
if(i < n-1 && f[j] <= s[i+1] && s[i+1] - mid <= f[j]){
dp[i+2] = max(dp[i+2], right[i]);
}
}
if(dp[n] == m){
r = mid;
}
else{
l = mid + 1;
}
}
int ans = l;
if(ans == mod){
cout<<-1<<endl;
return 0;
}
cout<<ans<<endl;
vector<int> right(n), us(n);
int ind = 0;
for(int i = 0; i < n; i++){
while(ind < m && s[i] + ans >= f[ind]) ind++;
right[i] = ind; // sağı sulayarak alabileceğim son çiçek + 1
}
ind = 0;
for(int i = 0; i < n; i++){
while(ind < m && s[i] >= f[ind]) ind++;
us[i] = ind; // benden büyük ilk çiçek
}
vector<int> dp(n+1); // dp[i] => ilk i tane sprinkle ile maximum alınabilecek flower prefixi
vector<int> d(n+1);
for(int i = 0; i < n; i++){
if(dp[i+1] < dp[i]){
dp[i+1] = dp[i];
d[i] = 0;
}
if(dp[i] == m) continue;
int j = dp[i];
if(f[j] <= s[i] && s[i] - ans <= f[j]){ // sola
if(dp[i+1] < us[i]){
dp[i+1] = us[i];
d[i] = 0;
}
}
if(f[j] >= s[i] && s[i] + ans <= f[j]){
if(dp[i+1] < right[i]){
dp[i+1] = right[i];
d[i] = 1;
}
}
if(i < n-1 && f[j] <= s[i+1] && s[i+1] - ans <= f[j]){
if(dp[i+2] < right[i]){
dp[i+2] = right[i];
d[i] = 1;
d[i+1] = 0;
}
}
}
for(int i = 0; i < n; i++){
if(d[i]) cout<<"R";
else cout<<"L";
}
cout<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Correct |
2 |
Correct |
1 ms |
336 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Correct |
2 |
Correct |
11 ms |
1872 KB |
Correct |
3 |
Incorrect |
1 ms |
336 KB |
User solution is worse than jury's solution |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Correct |
2 |
Incorrect |
10 ms |
2296 KB |
User solution is worse than jury's solution |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Correct |
2 |
Correct |
1 ms |
336 KB |
Correct |
3 |
Incorrect |
1 ms |
336 KB |
User solution is worse than jury's solution |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Correct |
2 |
Incorrect |
30 ms |
2792 KB |
User solution is incorrect |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Correct |
2 |
Correct |
1 ms |
336 KB |
Correct |
3 |
Correct |
11 ms |
1872 KB |
Correct |
4 |
Incorrect |
1 ms |
336 KB |
User solution is worse than jury's solution |
5 |
Halted |
0 ms |
0 KB |
- |