#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 = lower_bound(all(b),r+1)-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++;
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(a[f[1]],a[f[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)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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
8 ms |
1500 KB |
Correct |
3 |
Correct |
0 ms |
348 KB |
Correct |
4 |
Correct |
8 ms |
1500 KB |
Correct |
5 |
Correct |
10 ms |
1608 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
2 ms |
736 KB |
Correct |
9 |
Correct |
0 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
10 ms |
1500 KB |
Correct |
3 |
Correct |
5 ms |
844 KB |
Correct |
4 |
Correct |
59 ms |
4020 KB |
Correct |
5 |
Correct |
59 ms |
4004 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
67 ms |
4008 KB |
Correct |
9 |
Correct |
65 ms |
4008 KB |
Correct |
10 |
Correct |
88 ms |
3944 KB |
Correct |
11 |
Correct |
13 ms |
1500 KB |
Correct |
12 |
Correct |
32 ms |
2308 KB |
Correct |
13 |
Correct |
66 ms |
3772 KB |
Correct |
14 |
Correct |
66 ms |
3784 KB |
Correct |
15 |
Correct |
28 ms |
2776 KB |
Correct |
16 |
Correct |
70 ms |
3732 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
0 ms |
344 KB |
Correct |
4 |
Correct |
0 ms |
348 KB |
Correct |
5 |
Correct |
0 ms |
348 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
0 ms |
348 KB |
Correct |
9 |
Correct |
0 ms |
348 KB |
Correct |
10 |
Correct |
1 ms |
348 KB |
Correct |
11 |
Correct |
0 ms |
348 KB |
Correct |
12 |
Correct |
0 ms |
344 KB |
Correct |
13 |
Correct |
1 ms |
348 KB |
Correct |
14 |
Correct |
0 ms |
348 KB |
Correct |
15 |
Correct |
1 ms |
348 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
0 ms |
348 KB |
Correct |
18 |
Correct |
0 ms |
344 KB |
Correct |
19 |
Correct |
0 ms |
348 KB |
Correct |
20 |
Correct |
0 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
15 ms |
1492 KB |
Correct |
3 |
Correct |
51 ms |
2676 KB |
Correct |
4 |
Correct |
45 ms |
2776 KB |
Correct |
5 |
Correct |
46 ms |
2772 KB |
Correct |
6 |
Correct |
52 ms |
2632 KB |
Correct |
7 |
Correct |
81 ms |
3992 KB |
Correct |
8 |
Correct |
51 ms |
2772 KB |
Correct |
9 |
Correct |
50 ms |
2772 KB |
Correct |
10 |
Correct |
86 ms |
3988 KB |
Correct |
11 |
Correct |
47 ms |
2772 KB |
Correct |
12 |
Correct |
0 ms |
348 KB |
Correct |
13 |
Correct |
0 ms |
348 KB |
Correct |
14 |
Correct |
13 ms |
1500 KB |
Correct |
15 |
Correct |
17 ms |
1500 KB |
Correct |
16 |
Correct |
13 ms |
1500 KB |
Correct |
17 |
Correct |
14 ms |
2776 KB |
Correct |
18 |
Correct |
15 ms |
2776 KB |
Correct |
19 |
Correct |
17 ms |
2776 KB |
Correct |
20 |
Correct |
33 ms |
2776 KB |
Correct |
21 |
Correct |
34 ms |
2772 KB |
Correct |
22 |
Correct |
27 ms |
2632 KB |
Correct |
23 |
Incorrect |
25 ms |
2772 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 |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
8 ms |
1500 KB |
Correct |
4 |
Correct |
0 ms |
348 KB |
Correct |
5 |
Correct |
8 ms |
1500 KB |
Correct |
6 |
Correct |
10 ms |
1608 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
0 ms |
348 KB |
Correct |
9 |
Correct |
2 ms |
736 KB |
Correct |
10 |
Correct |
0 ms |
348 KB |
Correct |
11 |
Correct |
10 ms |
1500 KB |
Correct |
12 |
Correct |
5 ms |
844 KB |
Correct |
13 |
Correct |
59 ms |
4020 KB |
Correct |
14 |
Correct |
59 ms |
4004 KB |
Correct |
15 |
Correct |
0 ms |
348 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
67 ms |
4008 KB |
Correct |
18 |
Correct |
65 ms |
4008 KB |
Correct |
19 |
Correct |
88 ms |
3944 KB |
Correct |
20 |
Correct |
13 ms |
1500 KB |
Correct |
21 |
Correct |
32 ms |
2308 KB |
Correct |
22 |
Correct |
66 ms |
3772 KB |
Correct |
23 |
Correct |
66 ms |
3784 KB |
Correct |
24 |
Correct |
28 ms |
2776 KB |
Correct |
25 |
Correct |
70 ms |
3732 KB |
Correct |
26 |
Correct |
0 ms |
344 KB |
Correct |
27 |
Correct |
0 ms |
348 KB |
Correct |
28 |
Correct |
0 ms |
348 KB |
Correct |
29 |
Correct |
0 ms |
348 KB |
Correct |
30 |
Correct |
0 ms |
348 KB |
Correct |
31 |
Correct |
0 ms |
348 KB |
Correct |
32 |
Correct |
0 ms |
348 KB |
Correct |
33 |
Correct |
1 ms |
348 KB |
Correct |
34 |
Correct |
0 ms |
348 KB |
Correct |
35 |
Correct |
0 ms |
344 KB |
Correct |
36 |
Correct |
1 ms |
348 KB |
Correct |
37 |
Correct |
0 ms |
348 KB |
Correct |
38 |
Correct |
1 ms |
348 KB |
Correct |
39 |
Correct |
0 ms |
348 KB |
Correct |
40 |
Correct |
0 ms |
348 KB |
Correct |
41 |
Correct |
0 ms |
344 KB |
Correct |
42 |
Correct |
0 ms |
348 KB |
Correct |
43 |
Correct |
0 ms |
348 KB |
Correct |
44 |
Correct |
15 ms |
1492 KB |
Correct |
45 |
Correct |
51 ms |
2676 KB |
Correct |
46 |
Correct |
45 ms |
2776 KB |
Correct |
47 |
Correct |
46 ms |
2772 KB |
Correct |
48 |
Correct |
52 ms |
2632 KB |
Correct |
49 |
Correct |
81 ms |
3992 KB |
Correct |
50 |
Correct |
51 ms |
2772 KB |
Correct |
51 |
Correct |
50 ms |
2772 KB |
Correct |
52 |
Correct |
86 ms |
3988 KB |
Correct |
53 |
Correct |
47 ms |
2772 KB |
Correct |
54 |
Correct |
0 ms |
348 KB |
Correct |
55 |
Correct |
0 ms |
348 KB |
Correct |
56 |
Correct |
13 ms |
1500 KB |
Correct |
57 |
Correct |
17 ms |
1500 KB |
Correct |
58 |
Correct |
13 ms |
1500 KB |
Correct |
59 |
Correct |
14 ms |
2776 KB |
Correct |
60 |
Correct |
15 ms |
2776 KB |
Correct |
61 |
Correct |
17 ms |
2776 KB |
Correct |
62 |
Correct |
33 ms |
2776 KB |
Correct |
63 |
Correct |
34 ms |
2772 KB |
Correct |
64 |
Correct |
27 ms |
2632 KB |
Correct |
65 |
Incorrect |
25 ms |
2772 KB |
User solution is worse than jury's solution |
66 |
Halted |
0 ms |
0 KB |
- |