#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();
S.push_back(2000000001);
F.push_back(2000000001);
ans.assign(N, 0);
int buff = 0;
bool b = 0;
vector<int> next(N + 1), prev(N + 1), nextsprinkle(M + 1, N), after(N + 1);
next[N] = M;
prev[N] = M;
after[N] = M;
nextsprinkle[M] = N;
for (int i = 0; i < N; i++)
{
while (buff < M && F[buff] < S[i])
{
nextsprinkle[buff] = i;
buff++;
}
prev[i] = buff - 1;
next[i] = buff;
}
buff = 0;
for (int i = 0; i < N; i++)
{
while (buff < M && F[buff] - K <= S[i])
buff++;
after[i] = buff;
}
buff = 0;
vector<int> sprinkle, done(M + 1);
done[M] = 1;
int cover = -1000000001;
for (int i = 0; i < N; i++)
{
while (buff < M && F[buff] < S[i])
{
if (cover + K < F[buff])
b = 0;
else
done[buff] = 1;
buff++;
}
if (prev[i] == -1 || F[prev[i]] + K < S[i] || b == 1)
{
ans[i] = 1;
sprinkle.push_back(S[i]);
cover = S[i];
b = 1;
}
if (next[i] == M || F[next[i]] - K > S[i])
{
ans[i] = -1;
sprinkle.push_back(S[i] - K);
}
if (i > 0 && (prev[i] == -1 || S[i - 1] > F[prev[i]]))
{
ans[i] = 1;
sprinkle.push_back(S[i]);
cover = S[i];
b = 1;
ans[i - 1] = -1;
sprinkle.push_back(S[i - 1] - K);
}
}
while (buff < M)
{
if (cover + K < F[buff])
b = 0;
else
done[buff] = 1;
buff++;
}
buff = M - 1;
b = 0;
cover = 2000000001;
for (int i = N - 1; i >= 0; i--)
{
while (buff >= 0 && F[buff] > S[i])
{
if (cover - K > F[buff])
b = 0;
else
done[buff] = 1;
buff--;
}
if (b == 1)
{
cover = S[i];
sprinkle.push_back(S[i] - K);
ans[i] = -1;
}
if (ans[i] == -1)
{
cover = S[i];
b = 1;
}
}
while (buff >= 0)
{
if (cover - K > F[buff])
b = 0;
else
done[buff] = 1;
buff--;
}
vector<pair<int, int>> dp(M + 1);
vector<pair<vector<pair<int, int>>, vector<pair<int, int>>>> changes(M + 1);
vector<pair<int, int>> dp2(M + 1);
int donext = 0;
for (int i = 0; i < M; i++)
{
if (done[i])
continue;
if (donext <= i)
{
dp[i].first = 1;
dp2[i].first = -1;
donext = M + 10;
}
else if (donext != M + 10)
continue;
if (dp[i].first == 0)
continue;
if (S[nextsprinkle[i]] - K <= F[i])
{
if (done[next[nextsprinkle[i]]])
{
donext = next[nextsprinkle[i]];
ans[nextsprinkle[i]] = -1;
int x = i;
while (x != -1)
{
if (x >= N)
for (int j = 0; j < changes[x - N].second.size(); j++)
ans[changes[x - N].second[j].first] = changes[x - N].second[j].second;
else
for (int j = 0; j < changes[x].first.size(); j++)
ans[changes[x].first[j].first] = changes[x].first[j].second;
if (x >= N)
x = dp2[x - N].second;
else
x = dp2[x].first;
}
}
dp[next[nextsprinkle[i]]].first = 1;
dp2[next[nextsprinkle[i]]].first = i;
changes[next[nextsprinkle[i]]].first.push_back({nextsprinkle[i], -1});
if (nextsprinkle[i] < N && S[nextsprinkle[i] + 1] - K <= F[i])
{
if (done[after[nextsprinkle[i]]])
{
donext = after[nextsprinkle[i]];
ans[nextsprinkle[i]] = 1;
ans[nextsprinkle[i] + 1] = -1;
int x = i;
while (x != -1)
{
if (x >= N)
for (int j = 0; j < changes[x - N].second.size(); j++)
ans[changes[x - N].second[j].first] = changes[x - N].second[j].second;
else
for (int j = 0; j < changes[x].first.size(); j++)
ans[changes[x].first[j].first] = changes[x].first[j].second;
if (x >= N)
x = dp2[x - N].second;
else
x = dp2[x].first;
}
}
if (F[after[nextsprinkle[i]]] > S[nextsprinkle[i] + 2])
{
dp[after[nextsprinkle[i]]].second = 1;
dp2[after[nextsprinkle[i]]].second = i;
changes[after[nextsprinkle[i]]].second.push_back({nextsprinkle[i], 1});
changes[after[nextsprinkle[i]]].second.push_back({nextsprinkle[i] + 1, -1});
}
changes[after[nextsprinkle[i]]].first.push_back({nextsprinkle[i], 1});
changes[after[nextsprinkle[i]]].first.push_back({nextsprinkle[i] + 1, -1});
dp[after[nextsprinkle[i]]].first = 1;
dp2[after[nextsprinkle[i]]].first = i;
}
}
if (dp[i].second == 1)
{
if (done[after[nextsprinkle[i] - 1]])
{
donext = after[nextsprinkle[i] - 1];
ans[nextsprinkle[i] - 1] = 1;
int x = i + N;
while (x != -1)
{
if (x >= N)
for (int j = 0; j < changes[x - N].second.size(); j++)
ans[changes[x - N].second[j].first] = changes[x - N].second[j].second;
else
for (int j = 0; j < changes[x].first.size(); j++)
ans[changes[x].first[j].first] = changes[x].first[j].second;
if (x >= N)
x = dp2[x - N].second;
else
x = dp2[x].first;
}
}
dp[after[nextsprinkle[i] - 1]].first = 1;
dp2[after[nextsprinkle[i] - 1]].first = i + N;
changes[after[nextsprinkle[i] - 1]].first.push_back({nextsprinkle[i] - 1, 1});
if (F[after[nextsprinkle[i] - 1]] > S[nextsprinkle[i]])
{
dp[after[nextsprinkle[i] - 1]].second = 1;
dp2[after[nextsprinkle[i] - 1]].second = i + N;
changes[after[nextsprinkle[i] - 1]].second.push_back({nextsprinkle[i] - 1, 1});
}
}
}
F.pop_back();
S.pop_back();
if (donext != M + 10)
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:138:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (int j = 0; j < changes[x - N].second.size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:141:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for (int j = 0; j < changes[x].first.size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:163:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for (int j = 0; j < changes[x - N].second.size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:166:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | for (int j = 0; j < changes[x].first.size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:197:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
197 | for (int j = 0; j < changes[x - N].second.size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:200:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
200 | for (int j = 0; j < changes[x].first.size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:267:10: warning: unused variable 'b' [-Wunused-variable]
267 | bool b = solve(S, F, L, ans);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Correct |
| 2 |
Correct |
1 ms |
348 KB |
Correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Correct |
| 2 |
Correct |
46 ms |
7032 KB |
Correct |
| 3 |
Correct |
1 ms |
348 KB |
Correct |
| 4 |
Correct |
27 ms |
2264 KB |
Correct |
| 5 |
Correct |
26 ms |
2260 KB |
Correct |
| 6 |
Correct |
0 ms |
432 KB |
Correct |
| 7 |
Correct |
0 ms |
344 KB |
Correct |
| 8 |
Correct |
6 ms |
876 KB |
Correct |
| 9 |
Correct |
0 ms |
348 KB |
Correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Correct |
| 2 |
Correct |
58 ms |
9000 KB |
Correct |
| 3 |
Correct |
18 ms |
1300 KB |
Correct |
| 4 |
Correct |
256 ms |
14028 KB |
Correct |
| 5 |
Correct |
263 ms |
14100 KB |
Correct |
| 6 |
Correct |
1 ms |
344 KB |
Correct |
| 7 |
Correct |
0 ms |
348 KB |
Correct |
| 8 |
Correct |
157 ms |
8716 KB |
Correct |
| 9 |
Correct |
161 ms |
8852 KB |
Correct |
| 10 |
Correct |
226 ms |
12936 KB |
Correct |
| 11 |
Correct |
153 ms |
7356 KB |
Correct |
| 12 |
Correct |
119 ms |
10316 KB |
Correct |
| 13 |
Correct |
234 ms |
10376 KB |
Correct |
| 14 |
Correct |
229 ms |
11352 KB |
Correct |
| 15 |
Correct |
203 ms |
11452 KB |
Correct |
| 16 |
Correct |
186 ms |
7648 KB |
Correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Correct |
| 2 |
Correct |
1 ms |
348 KB |
Correct |
| 3 |
Correct |
1 ms |
344 KB |
Correct |
| 4 |
Correct |
1 ms |
348 KB |
Correct |
| 5 |
Correct |
2 ms |
348 KB |
Correct |
| 6 |
Incorrect |
1 ms |
448 KB |
User solution is incorrect |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Correct |
| 2 |
Correct |
64 ms |
8032 KB |
Correct |
| 3 |
Correct |
253 ms |
14856 KB |
Correct |
| 4 |
Correct |
260 ms |
15092 KB |
Correct |
| 5 |
Correct |
258 ms |
14484 KB |
Correct |
| 6 |
Correct |
272 ms |
14856 KB |
Correct |
| 7 |
Correct |
260 ms |
15056 KB |
Correct |
| 8 |
Correct |
253 ms |
15056 KB |
Correct |
| 9 |
Correct |
263 ms |
14884 KB |
Correct |
| 10 |
Correct |
294 ms |
14788 KB |
Correct |
| 11 |
Correct |
288 ms |
15052 KB |
Correct |
| 12 |
Correct |
0 ms |
348 KB |
Correct |
| 13 |
Correct |
1 ms |
348 KB |
Correct |
| 14 |
Correct |
144 ms |
7444 KB |
Correct |
| 15 |
Correct |
138 ms |
7448 KB |
Correct |
| 16 |
Correct |
129 ms |
7420 KB |
Correct |
| 17 |
Correct |
128 ms |
7400 KB |
Correct |
| 18 |
Correct |
154 ms |
7576 KB |
Correct |
| 19 |
Correct |
160 ms |
7788 KB |
Correct |
| 20 |
Correct |
256 ms |
14560 KB |
Correct |
| 21 |
Correct |
238 ms |
14504 KB |
Correct |
| 22 |
Correct |
251 ms |
13528 KB |
Correct |
| 23 |
Correct |
262 ms |
13700 KB |
Correct |
| 24 |
Correct |
189 ms |
7908 KB |
Correct |
| 25 |
Correct |
176 ms |
7924 KB |
Correct |
| 26 |
Correct |
133 ms |
6532 KB |
Correct |
| 27 |
Correct |
87 ms |
4660 KB |
Correct |
| 28 |
Correct |
243 ms |
10648 KB |
Correct |
| 29 |
Correct |
160 ms |
7700 KB |
Correct |
| 30 |
Correct |
168 ms |
8608 KB |
Correct |
| 31 |
Execution timed out |
2017 ms |
12164 KB |
Time limit exceeded |
| 32 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Correct |
| 2 |
Correct |
1 ms |
348 KB |
Correct |
| 3 |
Correct |
46 ms |
7032 KB |
Correct |
| 4 |
Correct |
1 ms |
348 KB |
Correct |
| 5 |
Correct |
27 ms |
2264 KB |
Correct |
| 6 |
Correct |
26 ms |
2260 KB |
Correct |
| 7 |
Correct |
0 ms |
432 KB |
Correct |
| 8 |
Correct |
0 ms |
344 KB |
Correct |
| 9 |
Correct |
6 ms |
876 KB |
Correct |
| 10 |
Correct |
0 ms |
348 KB |
Correct |
| 11 |
Correct |
58 ms |
9000 KB |
Correct |
| 12 |
Correct |
18 ms |
1300 KB |
Correct |
| 13 |
Correct |
256 ms |
14028 KB |
Correct |
| 14 |
Correct |
263 ms |
14100 KB |
Correct |
| 15 |
Correct |
1 ms |
344 KB |
Correct |
| 16 |
Correct |
0 ms |
348 KB |
Correct |
| 17 |
Correct |
157 ms |
8716 KB |
Correct |
| 18 |
Correct |
161 ms |
8852 KB |
Correct |
| 19 |
Correct |
226 ms |
12936 KB |
Correct |
| 20 |
Correct |
153 ms |
7356 KB |
Correct |
| 21 |
Correct |
119 ms |
10316 KB |
Correct |
| 22 |
Correct |
234 ms |
10376 KB |
Correct |
| 23 |
Correct |
229 ms |
11352 KB |
Correct |
| 24 |
Correct |
203 ms |
11452 KB |
Correct |
| 25 |
Correct |
186 ms |
7648 KB |
Correct |
| 26 |
Correct |
1 ms |
344 KB |
Correct |
| 27 |
Correct |
1 ms |
348 KB |
Correct |
| 28 |
Correct |
2 ms |
348 KB |
Correct |
| 29 |
Incorrect |
1 ms |
448 KB |
User solution is incorrect |
| 30 |
Halted |
0 ms |
0 KB |
- |
