#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
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];
if(n == 1) {
if(f[0] < s[0] && f[m-1] > s[0]) {
cout << -1 << endl;
return;
}
cout << max(abs(f[0]-s[0]), abs(f[m-1]-s[0])) << endl;
if(f[0] < s[0]) cout << "L" << endl;
else cout << "R" << endl;
} else if(n <= 10 && m <= 1000) {
string ans = "";
int cur = -1;
for(int i=0; i<(1LL<<n); ++i) {
string tmp = "";
int cnt = 0;
for(int j=0; j<n; ++j) {
if((1LL<<j)&i) tmp += "R";
else tmp += "L";
}
for(int j=0; j<m; ++j) {
bool found = 0;
int tmp2 = INT_MAX;
for(int k=0; k<n; ++k) {
if(s[k] >= f[j] && tmp[k] == 'L') {
tmp2 = min(tmp2, s[k] - f[j]);
found = 1;
break;
}
}
for(int k=n-1; k>=0; --k) {
if(s[k] <= f[j] && tmp[k] == 'R') {
tmp2 = min(tmp2, f[j] - s[k]);
found = 1;
break;
}
}
if(!found) {
cnt = -1;
break;
} else cnt = max(cnt, tmp2);
}
if(cnt != -1) {
if(cur == -1 or cnt < cur) {
cur = cnt;
ans = tmp;
}
}
}
if(cur == -1) cout << cur << endl;
else cout << cur << endl << ans << endl;
} else {
bool tc = 1;
if(n%3==0) {
for(int i=0; i<n/3; ++i) {
if(s[3*i+1]!=s[3*i+2] or s[3*i+1]!=s[3*i+3]) tc = 0;
}
} else tc = 0;
if(!tc) { // k <= 8
for(int k=0; k<=8; ++k) {
bool imp = 0;
int last = 0, R = -1;
vector<char>ans(n, 'L');
for(int i=0; i<m; ++i) {
if(f[i] <= R) continue;
if(last == n) {
imp = 1;
break;
}
if(s[last] <= f[i]) {
while(s[last]+k < f[i] && last < n) ++last;
if(last == n or s[last] > f[i]) {
imp = 1;
break;
}
ans[last] = 'R';
R = s[last] + k;
++last;
} else {
if(s[last] - k > f[i]) {
imp = 1;
break;
}
++last;
}
}
if(imp) continue;
cout << k << endl;
for(int i=0; i<n; ++i) cout << ans[i];
cout << endl;
return;
}
}
vector<pair<int,bool>>v;
for(int i=0; i<n; ++i) v.push_back({s[i], 1});
for(int i=0; i<m; ++i) v.push_back({f[i], 0});
sort(v.begin(), v.end());
int ans = 0, prev = -1;
vector<int>L(n+m, -1), R(n+m, -1);
for(int i=0; i<n+m; ++i) {
if(v[i].second) prev = v[i].first;
else L[i] = prev;
}
prev = -1;
for(int i=n+m-1; i>=0; --i) {
if(v[i].second) prev = v[i].first;
else R[i] = prev;
}
for(int i=0; i<n+m; ++i) {
if(v[i].second) continue;
if(L[i] == -1 && R[i] == -1) {
cout << -1 << endl;
return;
}
if(R[i] == -1) ans = max(ans, v[i].first - L[i]);
else if(L[i] == -1) ans = max(ans, R[i] - v[i].first);
else ans = max(ans, min(v[i].first - L[i], R[i] - v[i].first));
}
cout << ans << endl;
for(int i=0; i<n; i+=3) cout << "LLR";
cout << endl;
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while(t--) solve();
}
# |
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 |
6 ms |
1104 KB |
Correct |
3 |
Correct |
1 ms |
348 KB |
Correct |
4 |
Correct |
7 ms |
1116 KB |
Correct |
5 |
Correct |
8 ms |
1116 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
2 ms |
348 KB |
Correct |
9 |
Correct |
0 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
18 ms |
4304 KB |
Correct |
3 |
Correct |
2 ms |
992 KB |
Correct |
4 |
Correct |
37 ms |
8524 KB |
Correct |
5 |
Correct |
35 ms |
8860 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
24 ms |
8272 KB |
Correct |
9 |
Correct |
33 ms |
8980 KB |
Correct |
10 |
Correct |
38 ms |
9156 KB |
Correct |
11 |
Correct |
12 ms |
4304 KB |
Correct |
12 |
Correct |
17 ms |
5332 KB |
Correct |
13 |
Correct |
21 ms |
8400 KB |
Correct |
14 |
Correct |
22 ms |
7628 KB |
Correct |
15 |
Correct |
26 ms |
6852 KB |
Correct |
16 |
Correct |
20 ms |
6864 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
5 ms |
348 KB |
Correct |
4 |
Correct |
1 ms |
344 KB |
Correct |
5 |
Correct |
10 ms |
348 KB |
Correct |
6 |
Correct |
10 ms |
344 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
10 ms |
344 KB |
Correct |
9 |
Correct |
10 ms |
344 KB |
Correct |
10 |
Correct |
10 ms |
464 KB |
Correct |
11 |
Correct |
2 ms |
348 KB |
Correct |
12 |
Correct |
10 ms |
464 KB |
Correct |
13 |
Correct |
10 ms |
348 KB |
Correct |
14 |
Correct |
1 ms |
348 KB |
Correct |
15 |
Correct |
15 ms |
348 KB |
Correct |
16 |
Correct |
7 ms |
344 KB |
Correct |
17 |
Correct |
7 ms |
456 KB |
Correct |
18 |
Correct |
7 ms |
452 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 |
Incorrect |
20 ms |
4564 KB |
Incorrect string length |
3 |
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 |
6 ms |
1104 KB |
Correct |
4 |
Correct |
1 ms |
348 KB |
Correct |
5 |
Correct |
7 ms |
1116 KB |
Correct |
6 |
Correct |
8 ms |
1116 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
0 ms |
348 KB |
Correct |
9 |
Correct |
2 ms |
348 KB |
Correct |
10 |
Correct |
0 ms |
348 KB |
Correct |
11 |
Correct |
18 ms |
4304 KB |
Correct |
12 |
Correct |
2 ms |
992 KB |
Correct |
13 |
Correct |
37 ms |
8524 KB |
Correct |
14 |
Correct |
35 ms |
8860 KB |
Correct |
15 |
Correct |
0 ms |
348 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
24 ms |
8272 KB |
Correct |
18 |
Correct |
33 ms |
8980 KB |
Correct |
19 |
Correct |
38 ms |
9156 KB |
Correct |
20 |
Correct |
12 ms |
4304 KB |
Correct |
21 |
Correct |
17 ms |
5332 KB |
Correct |
22 |
Correct |
21 ms |
8400 KB |
Correct |
23 |
Correct |
22 ms |
7628 KB |
Correct |
24 |
Correct |
26 ms |
6852 KB |
Correct |
25 |
Correct |
20 ms |
6864 KB |
Correct |
26 |
Correct |
5 ms |
348 KB |
Correct |
27 |
Correct |
1 ms |
344 KB |
Correct |
28 |
Correct |
10 ms |
348 KB |
Correct |
29 |
Correct |
10 ms |
344 KB |
Correct |
30 |
Correct |
0 ms |
348 KB |
Correct |
31 |
Correct |
10 ms |
344 KB |
Correct |
32 |
Correct |
10 ms |
344 KB |
Correct |
33 |
Correct |
10 ms |
464 KB |
Correct |
34 |
Correct |
2 ms |
348 KB |
Correct |
35 |
Correct |
10 ms |
464 KB |
Correct |
36 |
Correct |
10 ms |
348 KB |
Correct |
37 |
Correct |
1 ms |
348 KB |
Correct |
38 |
Correct |
15 ms |
348 KB |
Correct |
39 |
Correct |
7 ms |
344 KB |
Correct |
40 |
Correct |
7 ms |
456 KB |
Correct |
41 |
Correct |
7 ms |
452 KB |
Correct |
42 |
Correct |
0 ms |
348 KB |
Correct |
43 |
Correct |
0 ms |
348 KB |
Correct |
44 |
Incorrect |
20 ms |
4564 KB |
Incorrect string length |
45 |
Halted |
0 ms |
0 KB |
- |