#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
int n,m;
vector<int> a,b;
void _(){
cin >> n >> m;
for(int i=0;i<n;i++){
int x; cin >> x;
a.push_back(x);
}
for(int i=0;i<m;i++){
int x;cin >> x;
b.push_back(x);
}
auto get = [&](int l,int r){
if(l>r) return -1LL;
int it = upper_bound(all(b),r)-b.begin();
int it2 = lower_bound(all(b),l)-b.begin();
return it-it2;
};
auto check = [&](int pow)->pair<bool,vector<char>>{
int p=0;
vector<char> res(n,'L');
for(int i=0;i<m;){
int lol=-1;
while(p<n && a[p]<=b[i]){
res[p]='R';
lol=max(lol,a[p]+pow);
p++;
}
if(lol>=b[i]){
while(i<m && lol>=b[i]) i++;
if(i==m) return {1,res};
continue;
}
if(i==m) return {1,res};
if(p==n) return {0,res};
vector<int> f;
while(p<n && a[p]-pow<=b[i]) f.push_back(p++);
if(sz(f)==0) return {0,res};
if(sz(f)==1){
while(i<m && b[i]<=a[f[0]]) i++;
continue;
}
if(sz(f)>=3){
for(int j=0;j<sz(f);j++){
if(j==sz(f)-2) continue;
res[f[j]]='R';
}
while(i<m && b[i]<=a[f.back()]+pow) i++;
if(i==m) return {1,res};
continue;
}
if(get(a[f[0]]+1,a[f[1]]-1)>0){
res[f[0]]='R';
while(i<m && b[i]<=max(f[1],a[0]+pow)) i++;
}
else{
res[f[1]]='R';
while(i<m && b[i]<=a[f.back()]+pow) i++;
}
}
return {1,res};
};
int l=0,r=(int)1e10;
while(l<r){
int m=(l+r)/2;
if(check(m).first) r=m;
else l=m+1;
}
if(r==(int)1e10) cout << -1 << '\n';
else{
auto X = check(l);
cout << l << '\n';
for(char x:X.second) cout << x;
cout << '\n';
}
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct |
2 |
Correct |
9 ms |
2264 KB |
Correct |
3 |
Correct |
0 ms |
348 KB |
Correct |
4 |
Correct |
9 ms |
2268 KB |
Correct |
5 |
Correct |
8 ms |
2268 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
1 ms |
348 KB |
Correct |
8 |
Correct |
2 ms |
900 KB |
Correct |
9 |
Correct |
0 ms |
452 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Correct |
2 |
Correct |
12 ms |
2464 KB |
Correct |
3 |
Correct |
3 ms |
940 KB |
Correct |
4 |
Correct |
29 ms |
5840 KB |
Correct |
5 |
Correct |
30 ms |
5840 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
31 ms |
5904 KB |
Correct |
9 |
Correct |
34 ms |
5912 KB |
Correct |
10 |
Correct |
59 ms |
5972 KB |
Correct |
11 |
Correct |
13 ms |
2332 KB |
Correct |
12 |
Correct |
15 ms |
3448 KB |
Correct |
13 |
Correct |
38 ms |
4764 KB |
Correct |
14 |
Correct |
34 ms |
4968 KB |
Correct |
15 |
Correct |
26 ms |
4052 KB |
Correct |
16 |
Correct |
37 ms |
4696 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Incorrect |
0 ms |
348 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 |
344 KB |
Correct |
2 |
Incorrect |
11 ms |
2680 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 |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
9 ms |
2264 KB |
Correct |
4 |
Correct |
0 ms |
348 KB |
Correct |
5 |
Correct |
9 ms |
2268 KB |
Correct |
6 |
Correct |
8 ms |
2268 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
1 ms |
348 KB |
Correct |
9 |
Correct |
2 ms |
900 KB |
Correct |
10 |
Correct |
0 ms |
452 KB |
Correct |
11 |
Correct |
12 ms |
2464 KB |
Correct |
12 |
Correct |
3 ms |
940 KB |
Correct |
13 |
Correct |
29 ms |
5840 KB |
Correct |
14 |
Correct |
30 ms |
5840 KB |
Correct |
15 |
Correct |
0 ms |
348 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
31 ms |
5904 KB |
Correct |
18 |
Correct |
34 ms |
5912 KB |
Correct |
19 |
Correct |
59 ms |
5972 KB |
Correct |
20 |
Correct |
13 ms |
2332 KB |
Correct |
21 |
Correct |
15 ms |
3448 KB |
Correct |
22 |
Correct |
38 ms |
4764 KB |
Correct |
23 |
Correct |
34 ms |
4968 KB |
Correct |
24 |
Correct |
26 ms |
4052 KB |
Correct |
25 |
Correct |
37 ms |
4696 KB |
Correct |
26 |
Incorrect |
0 ms |
348 KB |
User solution is worse than jury's solution |
27 |
Halted |
0 ms |
0 KB |
- |