#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int _1[4 * 1000 + 5], _2[4 * 1000 + 5];
bool dyn[4 * 1000 + 5][2][2 * 1000 + 5];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string wyn;
int n;
cin >> n;
for(int i = 1; i < (n << 1) + 1; ++i)
{
cin >> _1[i];
}
for(int i = 1; i < (n << 1) + 1; ++i)
{
cin >> _2[i];
}
dyn[1][0][1] = 1;
dyn[1][1][0] = 1;
for(int i = 2; i < (n << 1) + 1; ++i)
{
for(int j = 0; j < min(i, n) + 1; ++j)
{
dyn[i][0][j] = dyn[i - 1][0][j - 1] * (_1[i - 1] <= _1[i]) + dyn[i - 1][1][j - 1] * (_2[i - 1] <= _1[i]);
dyn[i][1][j] = dyn[i - 1][0][j] * (_1[i - 1] <= _2[i]) + dyn[i - 1][1][j] * (_2[i - 1] <= _2[i]);
}
}
if(dyn[(n << 1)][0][n] + dyn[(n << 1)][1][n] == 0)
{
cout << "-1\n";
return 0;
}
for(int i = (n << 1), ile = n; i > 0; --i)
{
if(dyn[i][0][ile] == 1 && (wyn.empty() || _1[i] <= (wyn.back() == 'B') * _2[i + 1] + (wyn.back() == 'A') * _1[i + 1]))
{
wyn += "A";
ile--;
}
else if(dyn[i][1][ile] == 1)
{
wyn += "B";
}
}
reverse(wyn.begin(), wyn.end());
cout << wyn << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
22 ms |
14976 KB |
Output is correct |
6 |
Correct |
22 ms |
14592 KB |
Output is correct |
7 |
Correct |
18 ms |
12928 KB |
Output is correct |
8 |
Correct |
22 ms |
13952 KB |
Output is correct |
9 |
Correct |
22 ms |
14336 KB |
Output is correct |
10 |
Correct |
18 ms |
12800 KB |
Output is correct |
11 |
Correct |
22 ms |
15232 KB |
Output is correct |
12 |
Correct |
25 ms |
16128 KB |
Output is correct |
13 |
Correct |
23 ms |
16128 KB |
Output is correct |
14 |
Correct |
24 ms |
16256 KB |
Output is correct |
15 |
Correct |
24 ms |
16128 KB |
Output is correct |
16 |
Correct |
27 ms |
16248 KB |
Output is correct |
17 |
Correct |
24 ms |
16120 KB |
Output is correct |
18 |
Correct |
26 ms |
16128 KB |
Output is correct |
19 |
Correct |
24 ms |
16128 KB |
Output is correct |
20 |
Correct |
23 ms |
16128 KB |
Output is correct |
21 |
Correct |
24 ms |
16128 KB |
Output is correct |
22 |
Correct |
24 ms |
16128 KB |
Output is correct |
23 |
Correct |
27 ms |
16120 KB |
Output is correct |
24 |
Correct |
25 ms |
16120 KB |
Output is correct |
25 |
Correct |
23 ms |
16000 KB |
Output is correct |
26 |
Correct |
23 ms |
16128 KB |
Output is correct |
27 |
Correct |
23 ms |
16128 KB |
Output is correct |
28 |
Correct |
21 ms |
14464 KB |
Output is correct |
29 |
Correct |
25 ms |
16128 KB |
Output is correct |
30 |
Correct |
23 ms |
14584 KB |
Output is correct |
31 |
Correct |
27 ms |
16120 KB |
Output is correct |
32 |
Correct |
19 ms |
13568 KB |
Output is correct |
33 |
Correct |
23 ms |
16128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
22 ms |
14976 KB |
Output is correct |
6 |
Correct |
22 ms |
14592 KB |
Output is correct |
7 |
Correct |
18 ms |
12928 KB |
Output is correct |
8 |
Correct |
22 ms |
13952 KB |
Output is correct |
9 |
Correct |
22 ms |
14336 KB |
Output is correct |
10 |
Correct |
18 ms |
12800 KB |
Output is correct |
11 |
Correct |
22 ms |
15232 KB |
Output is correct |
12 |
Correct |
25 ms |
16128 KB |
Output is correct |
13 |
Correct |
23 ms |
16128 KB |
Output is correct |
14 |
Correct |
24 ms |
16256 KB |
Output is correct |
15 |
Correct |
24 ms |
16128 KB |
Output is correct |
16 |
Correct |
27 ms |
16248 KB |
Output is correct |
17 |
Correct |
24 ms |
16120 KB |
Output is correct |
18 |
Correct |
26 ms |
16128 KB |
Output is correct |
19 |
Correct |
24 ms |
16128 KB |
Output is correct |
20 |
Correct |
23 ms |
16128 KB |
Output is correct |
21 |
Correct |
24 ms |
16128 KB |
Output is correct |
22 |
Correct |
24 ms |
16128 KB |
Output is correct |
23 |
Correct |
27 ms |
16120 KB |
Output is correct |
24 |
Correct |
25 ms |
16120 KB |
Output is correct |
25 |
Correct |
23 ms |
16000 KB |
Output is correct |
26 |
Correct |
23 ms |
16128 KB |
Output is correct |
27 |
Correct |
23 ms |
16128 KB |
Output is correct |
28 |
Correct |
21 ms |
14464 KB |
Output is correct |
29 |
Correct |
25 ms |
16128 KB |
Output is correct |
30 |
Correct |
23 ms |
14584 KB |
Output is correct |
31 |
Correct |
27 ms |
16120 KB |
Output is correct |
32 |
Correct |
19 ms |
13568 KB |
Output is correct |
33 |
Correct |
23 ms |
16128 KB |
Output is correct |
34 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
35 |
Halted |
0 ms |
0 KB |
- |