#include <bits/stdc++.h>
using namespace std;
template<typename T>
using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using pi = pair<int,int>;
vi water, flowers;
V<bool> types;
set<int> problems;
constexpr int inf = 1e9 + 7;
bool between(int l, int r) {
auto it = problems.upper_bound(l);
if (it == problems.end() || *it >= r) return true;
return false;
}
int pos(V<V<int>> &dp, int i, int lastR, int r) {
int leftR = -1;
if (i >= 0) {
for (int j = 0; j < 3; ++j) {
if (j == 0) leftR = water[i];
if (j == 1 && i - 1 >= 0) leftR = water[i - 1] + r;
if (j == 2) leftR = water[i] + r;
if (dp[i][j] == -1) continue;
if (between(leftR, lastR)) return j;
}
} else {
return between(0, lastR) ? 0 : -1;
}
return -1;
}
bool ok(int r) {
V<V<int>> dp(water.size() + 1, vi(3,-1));
for (int i = 0; i < water.size(); ++i) {
for (int j = 0; j < 3; ++j) {
int lastR = -1;
if (j == 0) lastR = water[i] - r;
if (j == 1 && between(water[i - 1] + r, water[i] - r)) lastR = water[i] - r;
if (j == 2) lastR = water[i];
dp[i][j] = pos(dp,i - 1 + (j == 1 ? -1 : 0),lastR, r);
}
}
// Backtrace
int last = dp[water.size() - 1][2];
int i = water.size() - 1;
if (last == -1) return false;
while (last != -1) {
if (last == 1) {
types.push_back(false);
types.push_back(true);
if (i - 2 < 0) return true;
last = dp[i - 2][last];
i -= 2;
} else {
types.push_back(last == 2);
if (i - 1 < 0) return true;
last = dp[i - 1][last];
i--;
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
water.resize(n + 1);
flowers.resize(m);
for (int i = 0; i < n; ++i) {
cin >> water[i];
water[i]++;
}
water[n] = inf;
for (int i = 0; i < m; ++i) {
cin >> flowers[i];
flowers[i]++;
problems.insert(flowers[i]);
}
int l = 0, r = inf; // Last true
while (r > l) {
int mid = l + (r - l) / 2;
if (ok(mid)) {
r = mid;
} else
l = mid + 1;
}
types.clear();
ok(l);
if (l == inf) {
cout << -1;
return 0;
}
if (l == 0 && problems.contains(water[0])) exit(5);
cout << l << "\n";
types.pop_back();
std::reverse(types.begin(), types.end());
for (auto x : types) {
cout << (x ? "R" : "L");
}
return 0;
}
Compilation message
Main.cpp: In function 'bool ok(int)':
Main.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i = 0; i < water.size(); ++i) {
| ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:105:28: error: 'class std::set<int>' has no member named 'contains'
105 | if (l == 0 && problems.contains(water[0])) exit(5);
| ^~~~~~~~
