#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 ll,int rr){
if(ll>rr) return -1LL;
int it = lower_bound(all(b),rr+1)-b.begin();
int it2 = lower_bound(all(b),ll)-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;){
if(p==n) return {0,res};
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++;
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++;
continue;
}
while(i<m && b[i]<=a[f[0]]) i++;
if(i==m) return {1,res};
if(b[i]>=a[f[1]]){
p--;
continue;
}
else{
res[f[0]]='R';
while(i<m && b[i]<=a[f[0]]+pow) i++;
}
}
return {1,res};
};
int l=0,r=(int)1e18;
while(l<r){
int m=(l+r)/2;
if(check(m).first) r=m;
else l=m+1;
}
if(r==(int)1e18) 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;
}
Compilation message
Main.cpp: In function 'void _()':
Main.cpp:22:8: warning: variable 'get' set but not used [-Wunused-but-set-variable]
22 | auto get = [&](int ll,int rr){
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct |
2 |
Correct |
8 ms |
2268 KB |
Correct |
3 |
Correct |
0 ms |
344 KB |
Correct |
4 |
Correct |
8 ms |
2524 KB |
Correct |
5 |
Correct |
9 ms |
2340 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
452 KB |
Correct |
8 |
Correct |
2 ms |
864 KB |
Correct |
9 |
Correct |
1 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct |
2 |
Correct |
13 ms |
2272 KB |
Correct |
3 |
Correct |
5 ms |
984 KB |
Correct |
4 |
Correct |
56 ms |
5920 KB |
Correct |
5 |
Correct |
59 ms |
5960 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
61 ms |
5988 KB |
Correct |
9 |
Correct |
61 ms |
5952 KB |
Correct |
10 |
Correct |
87 ms |
5972 KB |
Correct |
11 |
Correct |
13 ms |
2264 KB |
Correct |
12 |
Correct |
29 ms |
3544 KB |
Correct |
13 |
Correct |
72 ms |
4820 KB |
Correct |
14 |
Correct |
65 ms |
5056 KB |
Correct |
15 |
Correct |
27 ms |
4052 KB |
Correct |
16 |
Correct |
68 ms |
4748 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
0 ms |
348 KB |
Correct |
4 |
Correct |
1 ms |
460 KB |
Correct |
5 |
Correct |
1 ms |
348 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
452 KB |
Correct |
8 |
Correct |
0 ms |
348 KB |
Correct |
9 |
Correct |
1 ms |
460 KB |
Correct |
10 |
Correct |
0 ms |
348 KB |
Correct |
11 |
Correct |
0 ms |
348 KB |
Correct |
12 |
Correct |
0 ms |
348 KB |
Correct |
13 |
Correct |
0 ms |
348 KB |
Correct |
14 |
Correct |
0 ms |
348 KB |
Correct |
15 |
Correct |
0 ms |
348 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
0 ms |
348 KB |
Correct |
18 |
Correct |
0 ms |
348 KB |
Correct |
19 |
Correct |
0 ms |
348 KB |
Correct |
20 |
Correct |
1 ms |
344 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct |
2 |
Correct |
16 ms |
2516 KB |
Correct |
3 |
Correct |
45 ms |
4568 KB |
Correct |
4 |
Correct |
43 ms |
4564 KB |
Correct |
5 |
Correct |
42 ms |
4556 KB |
Correct |
6 |
Correct |
45 ms |
4568 KB |
Correct |
7 |
Correct |
77 ms |
5888 KB |
Correct |
8 |
Correct |
47 ms |
4568 KB |
Correct |
9 |
Correct |
45 ms |
4564 KB |
Correct |
10 |
Correct |
81 ms |
5936 KB |
Correct |
11 |
Correct |
46 ms |
4568 KB |
Correct |
12 |
Correct |
0 ms |
344 KB |
Correct |
13 |
Correct |
0 ms |
348 KB |
Correct |
14 |
Correct |
12 ms |
2520 KB |
Correct |
15 |
Correct |
13 ms |
2516 KB |
Correct |
16 |
Correct |
14 ms |
2520 KB |
Correct |
17 |
Correct |
15 ms |
3288 KB |
Correct |
18 |
Correct |
15 ms |
3540 KB |
Correct |
19 |
Correct |
17 ms |
3668 KB |
Correct |
20 |
Correct |
32 ms |
4308 KB |
Correct |
21 |
Correct |
32 ms |
4072 KB |
Correct |
22 |
Correct |
24 ms |
4052 KB |
Correct |
23 |
Incorrect |
25 ms |
4052 KB |
User solution is worse than jury's solution |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
8 ms |
2268 KB |
Correct |
4 |
Correct |
0 ms |
344 KB |
Correct |
5 |
Correct |
8 ms |
2524 KB |
Correct |
6 |
Correct |
9 ms |
2340 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
0 ms |
452 KB |
Correct |
9 |
Correct |
2 ms |
864 KB |
Correct |
10 |
Correct |
1 ms |
348 KB |
Correct |
11 |
Correct |
13 ms |
2272 KB |
Correct |
12 |
Correct |
5 ms |
984 KB |
Correct |
13 |
Correct |
56 ms |
5920 KB |
Correct |
14 |
Correct |
59 ms |
5960 KB |
Correct |
15 |
Correct |
0 ms |
348 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
61 ms |
5988 KB |
Correct |
18 |
Correct |
61 ms |
5952 KB |
Correct |
19 |
Correct |
87 ms |
5972 KB |
Correct |
20 |
Correct |
13 ms |
2264 KB |
Correct |
21 |
Correct |
29 ms |
3544 KB |
Correct |
22 |
Correct |
72 ms |
4820 KB |
Correct |
23 |
Correct |
65 ms |
5056 KB |
Correct |
24 |
Correct |
27 ms |
4052 KB |
Correct |
25 |
Correct |
68 ms |
4748 KB |
Correct |
26 |
Correct |
0 ms |
348 KB |
Correct |
27 |
Correct |
1 ms |
460 KB |
Correct |
28 |
Correct |
1 ms |
348 KB |
Correct |
29 |
Correct |
0 ms |
348 KB |
Correct |
30 |
Correct |
0 ms |
452 KB |
Correct |
31 |
Correct |
0 ms |
348 KB |
Correct |
32 |
Correct |
1 ms |
460 KB |
Correct |
33 |
Correct |
0 ms |
348 KB |
Correct |
34 |
Correct |
0 ms |
348 KB |
Correct |
35 |
Correct |
0 ms |
348 KB |
Correct |
36 |
Correct |
0 ms |
348 KB |
Correct |
37 |
Correct |
0 ms |
348 KB |
Correct |
38 |
Correct |
0 ms |
348 KB |
Correct |
39 |
Correct |
0 ms |
348 KB |
Correct |
40 |
Correct |
0 ms |
348 KB |
Correct |
41 |
Correct |
0 ms |
348 KB |
Correct |
42 |
Correct |
0 ms |
348 KB |
Correct |
43 |
Correct |
1 ms |
344 KB |
Correct |
44 |
Correct |
16 ms |
2516 KB |
Correct |
45 |
Correct |
45 ms |
4568 KB |
Correct |
46 |
Correct |
43 ms |
4564 KB |
Correct |
47 |
Correct |
42 ms |
4556 KB |
Correct |
48 |
Correct |
45 ms |
4568 KB |
Correct |
49 |
Correct |
77 ms |
5888 KB |
Correct |
50 |
Correct |
47 ms |
4568 KB |
Correct |
51 |
Correct |
45 ms |
4564 KB |
Correct |
52 |
Correct |
81 ms |
5936 KB |
Correct |
53 |
Correct |
46 ms |
4568 KB |
Correct |
54 |
Correct |
0 ms |
344 KB |
Correct |
55 |
Correct |
0 ms |
348 KB |
Correct |
56 |
Correct |
12 ms |
2520 KB |
Correct |
57 |
Correct |
13 ms |
2516 KB |
Correct |
58 |
Correct |
14 ms |
2520 KB |
Correct |
59 |
Correct |
15 ms |
3288 KB |
Correct |
60 |
Correct |
15 ms |
3540 KB |
Correct |
61 |
Correct |
17 ms |
3668 KB |
Correct |
62 |
Correct |
32 ms |
4308 KB |
Correct |
63 |
Correct |
32 ms |
4072 KB |
Correct |
64 |
Correct |
24 ms |
4052 KB |
Correct |
65 |
Incorrect |
25 ms |
4052 KB |
User solution is worse than jury's solution |
66 |
Halted |
0 ms |
0 KB |
- |