#include <bits/stdc++.h>
int main() {
using namespace std;
ios_base::sync_with_stdio(0);
int n; cin >> n;
vector<int> a(2 * n), b(2 * n);
for (int i = 0; i < 2 * n; i++)
cin >> a[i];
for (int i = 0; i < 2 * n; i++)
cin >> b[i];
// the dp states
vector<array<pair<int, int>, 2>> dp(2 * n);
// 0 stands for A, 1 stands for B
for (int i = 0; i < 2 * n; i++)
for (int j = 0; j < 2; j++)
dp[i][j].first = dp[i][j].second = -1;
dp[0][0] = {1, 1};
dp[0][1] = {0, 0};
for (int i = 1; i < 2 * n; i++) {
// if i end in A
if (a[i] >= a[i - 1] && dp[i - 1][0].first != -1) {
dp[i][0] = dp[i - 1][0];
dp[i][0].first++;
dp[i][0].second++;
}
if (a[i] >= b[i - 1] && dp[i - 1][1].first != -1) {
if (dp[i][0].first == -1) {
dp[i][0] = dp[i - 1][1];
dp[i][0].first++;
dp[i][0].second++;
} else {
dp[i][0].first = min(dp[i][0].first, dp[i - 1][1].first + 1);
dp[i][0].second = max(dp[i][0].second, dp[i - 1][1].second + 1);
}
}
if (b[i] >= a[i - 1] && dp[i - 1][0].first != -1) {
dp[i][1] = dp[i - 1][0];
}
if (b[i] >= b[i - 1] && dp[i - 1][1].first != -1) {
if (dp[i][1].first == -1) {
dp[i][1] = dp[i - 1][1];
} else {
dp[i][1].first = min(dp[i][1].first, dp[i - 1][1].first);
dp[i][1].second = max(dp[i][1].second, dp[i - 1][1].second);
}
}
}
auto in = [&](pair<int, int> p, int x) -> bool {
return p.first <= x && x <= p.second;
};
bool ok1 = in(dp[2 * n - 1][0], n);
bool ok2 = in(dp[2 * n - 1][1], n);
if (!ok1 && !ok2) {
cout << -1 << '\n';
} else {
int ci = 2 * n - 1, cj, cv = n;
if (ok1) {
cj = 0;
} else {
cj = 1;
}
string ans = "";
while (true) {
ans += (char) ('A' + cj);
if (ci == 0)
break;
if (cj == 0) {
if (a[ci - 1] <= a[ci] && in(dp[ci - 1][0], cv - 1)) {
cj = 0;
cv--;
} else {
cj = 1;
cv--;
}
} else {
if (a[ci - 1] <= b[ci] && in(dp[ci - 1][0], cv)) {
cj = 0;
} else {
cj = 1;
}
}
ci--;
}
reverse(ans.begin(), ans.end());
cout << ans << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
2 ms |
492 KB |
Output is correct |
6 |
Correct |
2 ms |
492 KB |
Output is correct |
7 |
Correct |
2 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
2 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
2 ms |
492 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
492 KB |
Output is correct |
14 |
Correct |
2 ms |
492 KB |
Output is correct |
15 |
Correct |
2 ms |
492 KB |
Output is correct |
16 |
Correct |
2 ms |
492 KB |
Output is correct |
17 |
Correct |
2 ms |
492 KB |
Output is correct |
18 |
Correct |
2 ms |
492 KB |
Output is correct |
19 |
Correct |
2 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
512 KB |
Output is correct |
22 |
Correct |
1 ms |
492 KB |
Output is correct |
23 |
Correct |
1 ms |
492 KB |
Output is correct |
24 |
Correct |
2 ms |
512 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
1 ms |
492 KB |
Output is correct |
27 |
Correct |
1 ms |
492 KB |
Output is correct |
28 |
Correct |
1 ms |
492 KB |
Output is correct |
29 |
Correct |
1 ms |
492 KB |
Output is correct |
30 |
Correct |
1 ms |
492 KB |
Output is correct |
31 |
Correct |
2 ms |
492 KB |
Output is correct |
32 |
Correct |
1 ms |
492 KB |
Output is correct |
33 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
2 ms |
492 KB |
Output is correct |
6 |
Correct |
2 ms |
492 KB |
Output is correct |
7 |
Correct |
2 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
2 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
2 ms |
492 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
492 KB |
Output is correct |
14 |
Correct |
2 ms |
492 KB |
Output is correct |
15 |
Correct |
2 ms |
492 KB |
Output is correct |
16 |
Correct |
2 ms |
492 KB |
Output is correct |
17 |
Correct |
2 ms |
492 KB |
Output is correct |
18 |
Correct |
2 ms |
492 KB |
Output is correct |
19 |
Correct |
2 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
512 KB |
Output is correct |
22 |
Correct |
1 ms |
492 KB |
Output is correct |
23 |
Correct |
1 ms |
492 KB |
Output is correct |
24 |
Correct |
2 ms |
512 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
1 ms |
492 KB |
Output is correct |
27 |
Correct |
1 ms |
492 KB |
Output is correct |
28 |
Correct |
1 ms |
492 KB |
Output is correct |
29 |
Correct |
1 ms |
492 KB |
Output is correct |
30 |
Correct |
1 ms |
492 KB |
Output is correct |
31 |
Correct |
2 ms |
492 KB |
Output is correct |
32 |
Correct |
1 ms |
492 KB |
Output is correct |
33 |
Correct |
1 ms |
492 KB |
Output is correct |
34 |
Correct |
278 ms |
42604 KB |
Output is correct |
35 |
Correct |
256 ms |
42020 KB |
Output is correct |
36 |
Correct |
251 ms |
41380 KB |
Output is correct |
37 |
Correct |
262 ms |
42148 KB |
Output is correct |
38 |
Correct |
260 ms |
42148 KB |
Output is correct |
39 |
Correct |
246 ms |
41380 KB |
Output is correct |
40 |
Correct |
266 ms |
44768 KB |
Output is correct |
41 |
Correct |
247 ms |
42404 KB |
Output is correct |
42 |
Correct |
265 ms |
43812 KB |
Output is correct |
43 |
Correct |
286 ms |
45280 KB |
Output is correct |
44 |
Correct |
288 ms |
45640 KB |
Output is correct |
45 |
Correct |
281 ms |
45536 KB |
Output is correct |
46 |
Correct |
265 ms |
45536 KB |
Output is correct |
47 |
Correct |
273 ms |
44384 KB |
Output is correct |
48 |
Correct |
261 ms |
44164 KB |
Output is correct |
49 |
Correct |
267 ms |
45024 KB |
Output is correct |
50 |
Correct |
280 ms |
44512 KB |
Output is correct |
51 |
Correct |
282 ms |
44640 KB |
Output is correct |
52 |
Correct |
210 ms |
33632 KB |
Output is correct |
53 |
Correct |
205 ms |
33632 KB |
Output is correct |
54 |
Correct |
187 ms |
33648 KB |
Output is correct |
55 |
Correct |
190 ms |
33248 KB |
Output is correct |
56 |
Correct |
272 ms |
45792 KB |
Output is correct |
57 |
Correct |
230 ms |
40288 KB |
Output is correct |
58 |
Correct |
232 ms |
40544 KB |
Output is correct |
59 |
Correct |
232 ms |
40544 KB |
Output is correct |
60 |
Correct |
224 ms |
38564 KB |
Output is correct |
61 |
Correct |
238 ms |
41056 KB |
Output is correct |
62 |
Correct |
233 ms |
40372 KB |
Output is correct |
63 |
Correct |
236 ms |
41056 KB |
Output is correct |
64 |
Correct |
227 ms |
39716 KB |
Output is correct |
65 |
Correct |
236 ms |
41056 KB |
Output is correct |