#include <bits/stdc++.h>
using ll = long long;
using namespace std;
template<typename T>
using V = vector<T>;
using vi = V<ll>;
using vb = V<bool>;
using pi = pair<ll,ll>;
vi water, flowers;
V<bool> types;
set<ll> problems;
constexpr ll inf = 1e9 * 2 + 7;
bool between(ll l, ll r) {
auto it = problems.upper_bound(l);
if (it == problems.end() || *it >= r) return true;
return false;
}
ll pos(V<V<ll>> &dp, ll i, ll lastR, ll r) {
ll leftR = -1;
if (i >= 0) {
for (ll 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(ll r) {
V<V<ll>> dp(water.size() + 1, vi(3,-1));
for (ll i = 0; i < water.size(); ++i) {
for (ll j = 0; j < 3; ++j) {
ll lastR = -1;
if (j == 0) lastR = water[i] - r;
if (j == 1 && i - 1 >= 0 && 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
ll last = dp[water.size() - 1][2];
ll i = water.size() - 1;
if (last == -1) return false;
while (last != -1) {
if (last == 1) {
types.push_back(false);
if (i - 2 < 0) return true;
types.push_back(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() {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false); cin.tie(nullptr);
ll n, m; cin >> n >> m;
water.resize(n + 1);
flowers.resize(m);
for (ll i = 0; i < n; ++i) {
cin >> water[i];
water[i]++;
}
water[n] = inf;
for (ll i = 0; i < m; ++i) {
cin >> flowers[i];
flowers[i]++;
problems.insert(flowers[i]);
}
ll l = 0, r = inf; // Last true
while (r > l) {
ll 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;
}
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(ll)':
Main.cpp:43:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (ll i = 0; i < water.size(); ++i) {
| ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:75:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
592 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
592 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
592 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
592 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
592 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
592 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
