#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <bitset>
#include <set>
#include <map>
typedef long long llong;
const int MAXN = 1000000 + 10;
const int INF = 1e9;
int a[MAXN][2], n;
int dpA[MAXN][2];
int dpB[MAXN][2];
char ans[MAXN];
void solve()
{
for (int i = 1 ; i <= 2*n ; ++i)
{
dpA[i][0] = dpB[i][0] = -INF;
dpA[i][1] = dpB[i][1] = -INF;
for (int last = 0 ; last <= 1 ; ++last)
{
if (a[i][0] >= a[i - 1][last])
{
dpA[i][0] = std::max(dpA[i][0], dpA[i - 1][last] + 1);
dpB[i][0] = std::max(dpB[i][0], dpB[i - 1][last]);
}
if (a[i][1] >= a[i - 1][last])
{
dpA[i][1] = std::max(dpA[i][1], dpA[i - 1][last]);
dpB[i][1] = std::max(dpB[i][1], dpB[i - 1][last] + 1);
}
}
}
if (std::max(dpA[2*n][0], dpA[2*n][1]) < n || std::max(dpB[2*n][0], dpB[2*n][1]) < n)
{
std::cout << -1 << '\n';
return;
}
a[2*n + 1][0] = INF;
int cntA = n, cntB = n;
int idx = 2*n, last = 0;
while (cntA >= 1 || cntB >= 1)
{
if (a[idx][0] <= a[idx + 1][last] && dpA[idx][0] >= cntA && dpB[idx][0] >= cntB)
{
ans[idx - 1] = 'A';
last = 0;
cntA--;
idx--;
continue;
}
if (a[idx][1] <= a[idx + 1][last] && dpA[idx][1] >= cntA && dpB[idx][1] >= cntB)
{
ans[idx - 1] = 'B';
last = 1;
cntB--;
idx--;
continue;
}
std::cout << -1 << '\n';
return;
}
ans[2*n] = '\0';
std::cout << ans << '\n';
}
void read()
{
std::cin >> n;
for (int i = 1 ; i <= 2*n ; ++i) std::cin >> a[i][0];
for (int i = 1 ; i <= 2*n ; ++i) std::cin >> a[i][1];
}
void fastIO()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIO();
read();
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
472 KB |
Output is correct |
7 |
Correct |
1 ms |
412 KB |
Output is correct |
8 |
Correct |
1 ms |
416 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
440 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
472 KB |
Output is correct |
14 |
Correct |
1 ms |
432 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
2 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
388 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
1 ms |
388 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
2 ms |
468 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
1 ms |
468 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
1 ms |
468 KB |
Output is correct |
33 |
Correct |
1 ms |
472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
472 KB |
Output is correct |
7 |
Correct |
1 ms |
412 KB |
Output is correct |
8 |
Correct |
1 ms |
416 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
440 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
472 KB |
Output is correct |
14 |
Correct |
1 ms |
432 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
2 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
388 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
1 ms |
388 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
2 ms |
468 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
1 ms |
468 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
1 ms |
468 KB |
Output is correct |
33 |
Correct |
1 ms |
472 KB |
Output is correct |
34 |
Correct |
211 ms |
25732 KB |
Output is correct |
35 |
Correct |
196 ms |
40480 KB |
Output is correct |
36 |
Correct |
225 ms |
41168 KB |
Output is correct |
37 |
Correct |
203 ms |
39152 KB |
Output is correct |
38 |
Correct |
208 ms |
39480 KB |
Output is correct |
39 |
Correct |
202 ms |
41160 KB |
Output is correct |
40 |
Correct |
221 ms |
27976 KB |
Output is correct |
41 |
Correct |
194 ms |
41988 KB |
Output is correct |
42 |
Correct |
202 ms |
29572 KB |
Output is correct |
43 |
Correct |
222 ms |
28288 KB |
Output is correct |
44 |
Correct |
227 ms |
28128 KB |
Output is correct |
45 |
Correct |
228 ms |
28260 KB |
Output is correct |
46 |
Correct |
207 ms |
28188 KB |
Output is correct |
47 |
Correct |
196 ms |
32576 KB |
Output is correct |
48 |
Correct |
204 ms |
35556 KB |
Output is correct |
49 |
Correct |
213 ms |
28284 KB |
Output is correct |
50 |
Correct |
226 ms |
31520 KB |
Output is correct |
51 |
Correct |
244 ms |
31500 KB |
Output is correct |
52 |
Correct |
143 ms |
33256 KB |
Output is correct |
53 |
Correct |
144 ms |
33280 KB |
Output is correct |
54 |
Correct |
127 ms |
33360 KB |
Output is correct |
55 |
Correct |
139 ms |
32976 KB |
Output is correct |
56 |
Correct |
218 ms |
28040 KB |
Output is correct |
57 |
Correct |
194 ms |
40152 KB |
Output is correct |
58 |
Correct |
177 ms |
40208 KB |
Output is correct |
59 |
Correct |
172 ms |
40304 KB |
Output is correct |
60 |
Correct |
178 ms |
38208 KB |
Output is correct |
61 |
Correct |
188 ms |
40792 KB |
Output is correct |
62 |
Correct |
179 ms |
40120 KB |
Output is correct |
63 |
Correct |
180 ms |
40780 KB |
Output is correct |
64 |
Correct |
177 ms |
39496 KB |
Output is correct |
65 |
Correct |
187 ms |
40676 KB |
Output is correct |