#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> &S, vector<int> &F, int K, vector<int> &ans)
{
int N = S.size(), M = F.size();
vector<pair<int, int>> dp(M + 1, {-1, -1});
vector<pair<vector<pair<int, int>>, vector<pair<int, int>>>> changes(M + 1);
dp[0].first = -2;
if (S[0] < F[0])
dp[0].second = -2;
for (int i = 0; i < M; i++)
{
if (dp[i].first != -1)
{
int x = lower_bound(S.begin(), S.end(), F[i]) - S.begin();
if (x != N && S[x] - K <= F[i])
{
int y = lower_bound(F.begin(), F.end(), S[x]) - F.begin();
dp[y].first = i;
changes[y].first = {{x, -1}};
if (x < N - 1 && y < M && S[x + 1] < F[y])
{
dp[y].second = i;
changes[y].second = {{x, -1}};
}
if (x < N - 1 && S[x + 1] - K <= F[i])
{
y = upper_bound(F.begin(), F.end(), S[x] + K) - F.begin();
dp[y].first = i;
changes[y].first = {{x, 1}, {x + 1, -1}};
if (x < N - 2 && y < M && S[x + 2] < F[y])
{
dp[y].second = i;
changes[y].second = {{x, 1}, {x + 1, -1}};
}
}
}
}
if (dp[i].second != -1)
{
int x = lower_bound(S.begin(), S.end(), F[i]) - S.begin() - 1;
if (x == -1)
continue;
if (S[x] + K < F[i])
continue;
int y = upper_bound(F.begin(), F.end(), S[x] + K) - F.begin();
dp[y].first = i + ((i == 0) ? 0 : M);
changes[y].first = {{x, 1}};
if (x < N - 1 && y < M && S[x + 1] < F[y])
{
dp[y].second = i + ((i == 0) ? 0 : M);
changes[y].second = {{x, 1}};
}
}
}
if (dp[M].first != -1 || dp[M].second != -1)
{
int x = 0;
if (dp[M].first != -1)
x = M;
else
x = M + M;
while (x != 0)
{
if (x > M)
{
for (int i = 0; i < changes[x - M].second.size(); i++)
ans[changes[x - M].second[i].first] = changes[x - M].second[i].second;
x = dp[x - M].second;
}
else
{
for (int i = 0; i < changes[x].first.size(); i++)
ans[changes[x].first[i].first] = changes[x].first[i].second;
x = dp[x].first;
}
}
return 1;
}
else
return 0;
}
int main()
{
int N, M;
cin >> N >> M;
vector<int> S(N), F(M), F2;
for (int i = 0; i < N; i++)
{
cin >> S[i];
}
for (int i = 0; i < M; i++)
{
cin >> F[i];
}
int buff = 0;
for (int i = 0; i < N; i++)
{
while (buff < M && F[buff] <= S[i])
{
if (F[buff] != S[i])
F2.push_back(F[buff]);
buff++;
}
}
while (buff < M)
F2.push_back(F[buff++]);
swap(F, F2);
if (N == 1 && F[0] < S[0] && F[M - 1] > S[0])
{
cout << -1;
return 0;
}
int L = 0, R = 1000000000;
vector<int> ans(N + 1);
while (L != R)
{
int m = (L + R) / 2;
if (solve(S, F, m, ans))
R = m;
else
L = m + 1;
}
bool b = solve(S, F, L, ans);
cout << L << endl;
for (int i = 0; i < N; i++)
cout << ((ans[i] == 1) ? 'R' : 'L');
}
Compilation message
Main.cpp: In function 'bool solve(std::vector<int>&, std::vector<int>&, int, std::vector<int>&)':
Main.cpp:68:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 0; i < changes[x - M].second.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:74:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i < changes[x].first.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:125:10: warning: unused variable 'b' [-Wunused-variable]
125 | bool b = solve(S, F, L, ans);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
37 ms |
5588 KB |
Correct |
3 |
Correct |
0 ms |
344 KB |
Correct |
4 |
Correct |
25 ms |
1476 KB |
Correct |
5 |
Correct |
26 ms |
1240 KB |
Correct |
6 |
Correct |
1 ms |
348 KB |
Correct |
7 |
Correct |
1 ms |
348 KB |
Correct |
8 |
Correct |
5 ms |
604 KB |
Correct |
9 |
Correct |
1 ms |
344 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Correct |
2 |
Correct |
45 ms |
6584 KB |
Correct |
3 |
Correct |
26 ms |
960 KB |
Correct |
4 |
Correct |
359 ms |
9924 KB |
Correct |
5 |
Correct |
379 ms |
9936 KB |
Correct |
6 |
Correct |
1 ms |
600 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
58 ms |
3008 KB |
Correct |
9 |
Correct |
58 ms |
3284 KB |
Correct |
10 |
Correct |
192 ms |
7152 KB |
Correct |
11 |
Correct |
29 ms |
1112 KB |
Correct |
12 |
Correct |
199 ms |
8848 KB |
Correct |
13 |
Correct |
249 ms |
7492 KB |
Correct |
14 |
Correct |
315 ms |
8620 KB |
Correct |
15 |
Correct |
271 ms |
8808 KB |
Correct |
16 |
Correct |
164 ms |
5300 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
1 ms |
348 KB |
Correct |
4 |
Correct |
1 ms |
348 KB |
Correct |
5 |
Correct |
1 ms |
348 KB |
Correct |
6 |
Correct |
1 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
1 ms |
420 KB |
Correct |
9 |
Correct |
1 ms |
344 KB |
Correct |
10 |
Correct |
1 ms |
348 KB |
Correct |
11 |
Correct |
1 ms |
360 KB |
Correct |
12 |
Correct |
1 ms |
348 KB |
Correct |
13 |
Correct |
1 ms |
348 KB |
Correct |
14 |
Correct |
1 ms |
348 KB |
Correct |
15 |
Correct |
1 ms |
348 KB |
Correct |
16 |
Correct |
1 ms |
348 KB |
Correct |
17 |
Correct |
1 ms |
348 KB |
Correct |
18 |
Correct |
1 ms |
348 KB |
Correct |
19 |
Correct |
1 ms |
444 KB |
Correct |
20 |
Correct |
1 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Correct |
2 |
Correct |
106 ms |
6132 KB |
Correct |
3 |
Correct |
446 ms |
9784 KB |
Correct |
4 |
Correct |
490 ms |
9828 KB |
Correct |
5 |
Correct |
451 ms |
11300 KB |
Correct |
6 |
Correct |
465 ms |
11580 KB |
Correct |
7 |
Correct |
474 ms |
11944 KB |
Correct |
8 |
Correct |
475 ms |
11816 KB |
Correct |
9 |
Correct |
482 ms |
11760 KB |
Correct |
10 |
Correct |
461 ms |
11684 KB |
Correct |
11 |
Correct |
482 ms |
11784 KB |
Correct |
12 |
Correct |
0 ms |
348 KB |
Correct |
13 |
Correct |
1 ms |
408 KB |
Correct |
14 |
Runtime error |
26 ms |
2992 KB |
Execution killed with signal 11 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
37 ms |
5588 KB |
Correct |
4 |
Correct |
0 ms |
344 KB |
Correct |
5 |
Correct |
25 ms |
1476 KB |
Correct |
6 |
Correct |
26 ms |
1240 KB |
Correct |
7 |
Correct |
1 ms |
348 KB |
Correct |
8 |
Correct |
1 ms |
348 KB |
Correct |
9 |
Correct |
5 ms |
604 KB |
Correct |
10 |
Correct |
1 ms |
344 KB |
Correct |
11 |
Correct |
45 ms |
6584 KB |
Correct |
12 |
Correct |
26 ms |
960 KB |
Correct |
13 |
Correct |
359 ms |
9924 KB |
Correct |
14 |
Correct |
379 ms |
9936 KB |
Correct |
15 |
Correct |
1 ms |
600 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
58 ms |
3008 KB |
Correct |
18 |
Correct |
58 ms |
3284 KB |
Correct |
19 |
Correct |
192 ms |
7152 KB |
Correct |
20 |
Correct |
29 ms |
1112 KB |
Correct |
21 |
Correct |
199 ms |
8848 KB |
Correct |
22 |
Correct |
249 ms |
7492 KB |
Correct |
23 |
Correct |
315 ms |
8620 KB |
Correct |
24 |
Correct |
271 ms |
8808 KB |
Correct |
25 |
Correct |
164 ms |
5300 KB |
Correct |
26 |
Correct |
1 ms |
348 KB |
Correct |
27 |
Correct |
1 ms |
348 KB |
Correct |
28 |
Correct |
1 ms |
348 KB |
Correct |
29 |
Correct |
1 ms |
348 KB |
Correct |
30 |
Correct |
0 ms |
348 KB |
Correct |
31 |
Correct |
1 ms |
420 KB |
Correct |
32 |
Correct |
1 ms |
344 KB |
Correct |
33 |
Correct |
1 ms |
348 KB |
Correct |
34 |
Correct |
1 ms |
360 KB |
Correct |
35 |
Correct |
1 ms |
348 KB |
Correct |
36 |
Correct |
1 ms |
348 KB |
Correct |
37 |
Correct |
1 ms |
348 KB |
Correct |
38 |
Correct |
1 ms |
348 KB |
Correct |
39 |
Correct |
1 ms |
348 KB |
Correct |
40 |
Correct |
1 ms |
348 KB |
Correct |
41 |
Correct |
1 ms |
348 KB |
Correct |
42 |
Correct |
1 ms |
444 KB |
Correct |
43 |
Correct |
1 ms |
348 KB |
Correct |
44 |
Correct |
106 ms |
6132 KB |
Correct |
45 |
Correct |
446 ms |
9784 KB |
Correct |
46 |
Correct |
490 ms |
9828 KB |
Correct |
47 |
Correct |
451 ms |
11300 KB |
Correct |
48 |
Correct |
465 ms |
11580 KB |
Correct |
49 |
Correct |
474 ms |
11944 KB |
Correct |
50 |
Correct |
475 ms |
11816 KB |
Correct |
51 |
Correct |
482 ms |
11760 KB |
Correct |
52 |
Correct |
461 ms |
11684 KB |
Correct |
53 |
Correct |
482 ms |
11784 KB |
Correct |
54 |
Correct |
0 ms |
348 KB |
Correct |
55 |
Correct |
1 ms |
408 KB |
Correct |
56 |
Runtime error |
26 ms |
2992 KB |
Execution killed with signal 11 |
57 |
Halted |
0 ms |
0 KB |
- |