#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2002;
int n,a[2*N],b[2*N];
int dp[2*N][2*N][2];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= 2*n; i++){
cin >> a[i];
}
for(int i = 1; i <= 2*n; i++){
cin >> b[i];
}
dp[0][0][0] = dp[0][0][1] = 1;
for(int i = 1; i <= 2*n; i++){
for(int j = 0; j <= i; j++){
if(j > 0 && a[i] >= a[i-1]) dp[i][j][0] |= dp[i-1][j-1][0];
if(j > 0 && a[i] >= b[i-1]) dp[i][j][0] |= dp[i-1][j-1][1];
if(b[i] >= a[i-1]) dp[i][j][1] |= dp[i-1][j][0];
if(b[i] >= b[i-1]) dp[i][j][1] |= dp[i-1][j][1];
}
}
int x = 2*n,y = n,z = 0;
if(dp[x][y][z] == 0) z = 1;
if(dp[x][y][z] == 0){
cout << -1 << endl;
return 0;
}
string s = "";
while(x){
if(z == 0){
assert(y > 0);
s += "A";
if(a[x] >= a[x-1] && dp[x-1][y-1][0]){
x--;
y--;
z = 0;
}
else{
assert(a[x] >= b[x-1] && dp[x-1][y-1][1]);
x--;
y--;
z = 1;
}
}
else{
s += "B";
if(b[x] >= a[x-1] && dp[x-1][y][0]){
x--;
z = 0;
}
else{
assert(b[x] >= b[x-1] && dp[x-1][y][1]);
x--;
z = 1;
}
}
}
reverse(s.begin(),s.end());
cout << s << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
35 ms |
57420 KB |
Output is correct |
6 |
Correct |
37 ms |
65412 KB |
Output is correct |
7 |
Correct |
28 ms |
52920 KB |
Output is correct |
8 |
Correct |
34 ms |
60364 KB |
Output is correct |
9 |
Correct |
34 ms |
62760 KB |
Output is correct |
10 |
Correct |
27 ms |
51660 KB |
Output is correct |
11 |
Correct |
36 ms |
70252 KB |
Output is correct |
12 |
Correct |
42 ms |
77968 KB |
Output is correct |
13 |
Correct |
43 ms |
78044 KB |
Output is correct |
14 |
Correct |
46 ms |
78036 KB |
Output is correct |
15 |
Correct |
42 ms |
78036 KB |
Output is correct |
16 |
Correct |
42 ms |
78044 KB |
Output is correct |
17 |
Correct |
45 ms |
77900 KB |
Output is correct |
18 |
Correct |
43 ms |
78048 KB |
Output is correct |
19 |
Correct |
43 ms |
78072 KB |
Output is correct |
20 |
Correct |
44 ms |
77944 KB |
Output is correct |
21 |
Correct |
46 ms |
78008 KB |
Output is correct |
22 |
Correct |
45 ms |
78036 KB |
Output is correct |
23 |
Correct |
44 ms |
77960 KB |
Output is correct |
24 |
Correct |
43 ms |
78016 KB |
Output is correct |
25 |
Correct |
42 ms |
77348 KB |
Output is correct |
26 |
Correct |
41 ms |
78028 KB |
Output is correct |
27 |
Correct |
41 ms |
78060 KB |
Output is correct |
28 |
Correct |
35 ms |
64732 KB |
Output is correct |
29 |
Correct |
41 ms |
78012 KB |
Output is correct |
30 |
Correct |
34 ms |
65236 KB |
Output is correct |
31 |
Correct |
44 ms |
78028 KB |
Output is correct |
32 |
Correct |
31 ms |
57812 KB |
Output is correct |
33 |
Correct |
42 ms |
78028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
35 ms |
57420 KB |
Output is correct |
6 |
Correct |
37 ms |
65412 KB |
Output is correct |
7 |
Correct |
28 ms |
52920 KB |
Output is correct |
8 |
Correct |
34 ms |
60364 KB |
Output is correct |
9 |
Correct |
34 ms |
62760 KB |
Output is correct |
10 |
Correct |
27 ms |
51660 KB |
Output is correct |
11 |
Correct |
36 ms |
70252 KB |
Output is correct |
12 |
Correct |
42 ms |
77968 KB |
Output is correct |
13 |
Correct |
43 ms |
78044 KB |
Output is correct |
14 |
Correct |
46 ms |
78036 KB |
Output is correct |
15 |
Correct |
42 ms |
78036 KB |
Output is correct |
16 |
Correct |
42 ms |
78044 KB |
Output is correct |
17 |
Correct |
45 ms |
77900 KB |
Output is correct |
18 |
Correct |
43 ms |
78048 KB |
Output is correct |
19 |
Correct |
43 ms |
78072 KB |
Output is correct |
20 |
Correct |
44 ms |
77944 KB |
Output is correct |
21 |
Correct |
46 ms |
78008 KB |
Output is correct |
22 |
Correct |
45 ms |
78036 KB |
Output is correct |
23 |
Correct |
44 ms |
77960 KB |
Output is correct |
24 |
Correct |
43 ms |
78016 KB |
Output is correct |
25 |
Correct |
42 ms |
77348 KB |
Output is correct |
26 |
Correct |
41 ms |
78028 KB |
Output is correct |
27 |
Correct |
41 ms |
78060 KB |
Output is correct |
28 |
Correct |
35 ms |
64732 KB |
Output is correct |
29 |
Correct |
41 ms |
78012 KB |
Output is correct |
30 |
Correct |
34 ms |
65236 KB |
Output is correct |
31 |
Correct |
44 ms |
78028 KB |
Output is correct |
32 |
Correct |
31 ms |
57812 KB |
Output is correct |
33 |
Correct |
42 ms |
78028 KB |
Output is correct |
34 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
35 |
Halted |
0 ms |
0 KB |
- |