#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int> s, f;
set<int> fs;
map<int,int> g;
int gt(int x){
auto it = fs.lower_bound(x);
if (it == fs.end()) return -1;
return g[*it];
}
int lt(int x){
auto it = fs.upper_bound(x);
if (it == fs.begin()) return -1;
it--;
return g[*it];
}
pair<bool,string> check(int k){
string res = "";
for (int i=0; i<n; i++) res += 'R';
vector<int> dp(n+1, -1);
for (int i=0; i<n; i++){
//try left
int l = gt(s[i]-k), r = lt(s[i]);
if (dp[i] >= l-1 && dp[i+1] < r){
dp[i+1] = r;
res[i] = 'L';
}
//try right
l = gt(s[i]), r = lt(s[i]+k);
if (dp[i] >= l-1 && dp[i+1] < r){
dp[i+1] = r;
res[i] = 'R';
}
if (i == 0) continue;
//try right left
if (s[i]-s[i-1] > k) continue;
l = gt(s[i]-k), r = lt(s[i-1]+k);
if (dp[i-1] >= l-1 && dp[i+1] < r){
dp[i+1] = r;
res[i-1] = 'R';
res[i] = 'L';
}
}
if (dp[n] == m-1) return {true, res};
return {false, res};
}
signed main(){
cin >> n >> m;
s.resize(n);
f.resize(m);
for (int i=0; i<n; i++) cin >> s[i];
for (int i=0; i<m; i++){
cin >> f[i];
fs.insert(f[i]);
g[f[i]] = i;
}
int l = -1, r = pow(10, 9)+1;
while (l < r-1){
//cout << l << " " << r << endl;
int mid = (l+r)/2;
if (check(mid).first) r = mid;
else l = mid;
}
if (r == pow(10, 9)+1) cout << -1 << endl;
else cout << r << endl << check(r).second << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |