//-------------dilanyan------------\\
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
//------------------Kargpefines--------------------\\
#define ll long long
#define pb push_back
#define all(u) (u).begin(), (u).end()
#define pqueue priority_queue
#define upper upper_bound
#define lower lower_bound
#define umap unordered_map
#define uset unordered_set
void KarginSet(string name = "") {
ios_base::sync_with_stdio(false); cin.tie(NULL);
if (name.size()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
//-------------------KarginConstants------------------\\
const ll mod = 1e9 + 7;
const ll inf = 2e9;
//-------------------KarginCode-----------------------\\
const int N = 100005, M = 1000005;
int n, m;
int s[N], f[N];
int dp[N], d[N];
void KarginSolve() {
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> s[i];
for (int i = 1;i <= m;i++) cin >> f[i];
ll l = 0, r = 1e9, ans = -1;
vector<pair<int, char>> from(n + 1), bfrom(n + 1);
while (l <= r) {
ll mid = (l + r) / 2;
for (int i = 0; i <= n;i++) dp[i] = 0, bfrom[i] = { 0,'?' }; // lx[i] = 0, rx[i] = 0;
for (int i = 0;i < n;i++) {
if (f[dp[i] + 1] < s[i + 1]) {
if (f[dp[i] + 1] >= s[i + 1] - mid) {
int j = upper(f + 1 + dp[i], f + m + 1, s[i + 1]) - f - 1;
if (dp[i + 1] < j) {
dp[i + 1] = j;
bfrom[i + 1] = { i,'L' };
}
}
}
else {
int j = upper(f + 1 + dp[i], f + 1 + m, s[i + 1] + mid) - f - 1;
if (dp[i + 1] < j) {
dp[i + 1] = j;
bfrom[i + 1] = { i,'R' };
}
}
if (i + 2 <= n && f[dp[i] + 1] >= s[i + 2] - mid) {
int j = upper(f + 1 + dp[i], f + m + 1, s[i + 2]) - f - 1;
int jj = upper(f + 1 + dp[i], f + m + 1, s[i + 1] + mid) - f - 1;
if (dp[i + 2] < max(j,jj)) {
dp[i + 2] = max(j, jj);
bfrom[i + 2] = { i,'?' };
}
}
}
if (dp[n] == m) {
r = mid - 1;
ans = mid;
swap(from, bfrom);
}
else {
l = mid + 1;
}
}
cout << ans << '\n';
if (ans == -1) return;
int x = n;
vector<char> answ(n + 1);
while (x != 0) {
if (from[x].first == x - 2) {
answ[x] = 'L', answ[x - 1] = 'R';
x -= 2;
}
else {
answ[x] = from[x].second;
x--;
}
}
for (int i = 1;i <= n;i++) cout << answ[i];
}
int main() {
KarginSet();
int test = 1;
//cin >> test;
while (test--) {
KarginSolve();
}
return 0;
};
Compilation message
Main.cpp:1:1: warning: multi-line comment [-Wcomment]
1 | //-------------dilanyan------------\\
| ^
Main.cpp:8:1: warning: multi-line comment [-Wcomment]
8 | //------------------Kargpefines--------------------\\
| ^
Main.cpp:27:1: warning: multi-line comment [-Wcomment]
27 | //-------------------KarginConstants------------------\\
| ^
Main.cpp:32:1: warning: multi-line comment [-Wcomment]
32 | //-------------------KarginCode-----------------------\\
| ^
Main.cpp: In function 'void KarginSet(std::string)':
Main.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct |
2 |
Correct |
5 ms |
600 KB |
Correct |
3 |
Correct |
1 ms |
348 KB |
Correct |
4 |
Correct |
5 ms |
860 KB |
Correct |
5 |
Correct |
6 ms |
860 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
1 ms |
348 KB |
Correct |
9 |
Correct |
0 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct |
2 |
Incorrect |
7 ms |
856 KB |
Invalid character in the string |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Incorrect |
0 ms |
344 KB |
User solution is worse than jury's solution |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct |
2 |
Incorrect |
10 ms |
1112 KB |
User solution is worse than jury's solution |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
5 ms |
600 KB |
Correct |
4 |
Correct |
1 ms |
348 KB |
Correct |
5 |
Correct |
5 ms |
860 KB |
Correct |
6 |
Correct |
6 ms |
860 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
0 ms |
348 KB |
Correct |
9 |
Correct |
1 ms |
348 KB |
Correct |
10 |
Correct |
0 ms |
348 KB |
Correct |
11 |
Incorrect |
7 ms |
856 KB |
Invalid character in the string |
12 |
Halted |
0 ms |
0 KB |
- |