#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end()
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int MAXN = 2100;
template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }
int dp[2 * MAXN][MAXN][2][2]; //[index][number of a's used][current (b is 0, a is 1)][last]
int a[2 * MAXN], b[2 * MAXN];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
//freopen("1.in", "r", stdin);
//freopen("output.out", "w", stdout);
int n;
cin >> n;
repn(i, 1, 2 * n + 1) cin >> a[i];
repn(i, 1, 2 * n + 1) cin >> b[i];
rep(i, 2 * n + 1) rep(j, n + 1) rep(k, 2) rep(l, 2) dp[i][j][k][l] = 0;
if(a[2] >= a[1]) dp[2][2][1][1] = 1;
if(a[2] >= b[1]) dp[2][1][1][0] = 1;
if(b[2] >= a[1]) dp[2][1][0][1] = 1;
if(b[2] >= b[1]) dp[2][0][0][0] = 1;
repn(i, 3, 2 * n + 1){
rep(j, min(n + 1, i + 1)){
int cur = i;
int last = i - 1;
if(a[i] >= a[i - 1]){
if(j){
if(dp[last][j - 1][1][1]) dp[cur][j][1][1] = 1;
else if(dp[last][j - 1][1][0]) dp[cur][j][1][1] = 1;
}
}
if(a[i] >= b[i - 1]){
if(j){
if(dp[last][j - 1][0][0]) dp[cur][j][1][0] = 1;
else if(dp[last][j - 1][0][1]) dp[cur][j][1][0] = 1;
}
}
if(b[i] >= a[i - 1]){
if(dp[last][j][1][0]) dp[cur][j][0][1] = 1;
else if(dp[last][j][1][1]) dp[cur][j][0][1] = 1;
}
if(b[i] >= b[i - 1]){
if(dp[last][j][0][0]) dp[cur][j][0][0] = 1;
else if(dp[last][j][0][1]) dp[cur][j][0][0] = 1;
}
}
}
//now we need to reconstruct the answer
if(dp[2 * n][n][0][0]){
string ans = "B";
int lst = 0;
int ind = 2 * n - 1;
int cur = n;
while(ans.size() != 2 * n){
int f = 0;
if(lst) ans += 'A', f = 1;
else ans += 'B';
if(dp[ind][cur][lst][0]) lst = 0;
else if(dp[ind][cur][lst][1]) lst = 1;
if(f) cur--;
ind--;
}
reverse(all(ans));
cout << ans << endl;
}
else if(dp[2 * n][n][0][1]){
string ans = "B";
int lst = 1;
int ind = 2 * n - 1;
int cur = n;
while(ans.size() != 2 * n){
int f = 0;
if(lst) ans += 'A', f = 1;
else ans += 'B';
if(dp[ind][cur][lst][0]) lst = 0;
else if(dp[ind][cur][lst][1]) lst = 1;
if(f) cur--;
ind--;
}
reverse(all(ans));
cout << ans << endl;
}
else if(dp[2 * n][n][1][1]){
string ans = "A";
int lst = 1;
int ind = 2 * n - 1;
int cur = n - 1;
while(ans.size() != 2 * n){
int f = 0;
if(lst) ans += 'A', f = 1;
else ans += 'B';
if(dp[ind][cur][lst][0]) lst = 0;
else if(dp[ind][cur][lst][1]) lst = 1;
if(f) cur--;
ind--;
}
reverse(all(ans));
cout << ans << endl;
}
else if(dp[2 * n][n][1][0]){
string ans = "A";
int lst = 0;
int ind = 2 * n - 1;
int cur = n - 1;
while(ans.size() != 2 * n){
int f = 0;
if(lst) ans += 'A', f = 1;
else ans += 'B';
if(dp[ind][cur][lst][0]) lst = 0;
else if(dp[ind][cur][lst][1]) lst = 1;
if(f) cur--;
ind--;
}
reverse(all(ans));
cout << ans << endl;
}
else{
cout << -1 << endl;
return 0;
}
return 0;
}
/*
Things to look out for:
- Integer overflows
- Array bounds
- Special cases
Be careful!
*/
Compilation message
building4.cpp: In function 'int main()':
building4.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ans.size() != 2 * n){
~~~~~~~~~~~^~~~~~~~
building4.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ans.size() != 2 * n){
~~~~~~~~~~~^~~~~~~~
building4.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ans.size() != 2 * n){
~~~~~~~~~~~^~~~~~~~
building4.cpp:125:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ans.size() != 2 * n){
~~~~~~~~~~~^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
83 ms |
121848 KB |
Output is correct |
6 |
Correct |
85 ms |
116216 KB |
Output is correct |
7 |
Correct |
68 ms |
92792 KB |
Output is correct |
8 |
Correct |
76 ms |
106748 KB |
Output is correct |
9 |
Correct |
79 ms |
111480 KB |
Output is correct |
10 |
Correct |
63 ms |
90360 KB |
Output is correct |
11 |
Correct |
87 ms |
123768 KB |
Output is correct |
12 |
Correct |
97 ms |
131960 KB |
Output is correct |
13 |
Correct |
101 ms |
131960 KB |
Output is correct |
14 |
Correct |
97 ms |
131960 KB |
Output is correct |
15 |
Correct |
102 ms |
131960 KB |
Output is correct |
16 |
Correct |
99 ms |
131960 KB |
Output is correct |
17 |
Correct |
98 ms |
131832 KB |
Output is correct |
18 |
Correct |
101 ms |
131960 KB |
Output is correct |
19 |
Correct |
98 ms |
131960 KB |
Output is correct |
20 |
Correct |
98 ms |
131960 KB |
Output is correct |
21 |
Correct |
96 ms |
131960 KB |
Output is correct |
22 |
Correct |
106 ms |
131960 KB |
Output is correct |
23 |
Correct |
104 ms |
132180 KB |
Output is correct |
24 |
Correct |
95 ms |
131960 KB |
Output is correct |
25 |
Correct |
96 ms |
131196 KB |
Output is correct |
26 |
Correct |
98 ms |
131960 KB |
Output is correct |
27 |
Correct |
91 ms |
131960 KB |
Output is correct |
28 |
Correct |
84 ms |
114936 KB |
Output is correct |
29 |
Correct |
97 ms |
131960 KB |
Output is correct |
30 |
Correct |
84 ms |
115832 KB |
Output is correct |
31 |
Correct |
97 ms |
131960 KB |
Output is correct |
32 |
Correct |
78 ms |
101880 KB |
Output is correct |
33 |
Correct |
97 ms |
131960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
83 ms |
121848 KB |
Output is correct |
6 |
Correct |
85 ms |
116216 KB |
Output is correct |
7 |
Correct |
68 ms |
92792 KB |
Output is correct |
8 |
Correct |
76 ms |
106748 KB |
Output is correct |
9 |
Correct |
79 ms |
111480 KB |
Output is correct |
10 |
Correct |
63 ms |
90360 KB |
Output is correct |
11 |
Correct |
87 ms |
123768 KB |
Output is correct |
12 |
Correct |
97 ms |
131960 KB |
Output is correct |
13 |
Correct |
101 ms |
131960 KB |
Output is correct |
14 |
Correct |
97 ms |
131960 KB |
Output is correct |
15 |
Correct |
102 ms |
131960 KB |
Output is correct |
16 |
Correct |
99 ms |
131960 KB |
Output is correct |
17 |
Correct |
98 ms |
131832 KB |
Output is correct |
18 |
Correct |
101 ms |
131960 KB |
Output is correct |
19 |
Correct |
98 ms |
131960 KB |
Output is correct |
20 |
Correct |
98 ms |
131960 KB |
Output is correct |
21 |
Correct |
96 ms |
131960 KB |
Output is correct |
22 |
Correct |
106 ms |
131960 KB |
Output is correct |
23 |
Correct |
104 ms |
132180 KB |
Output is correct |
24 |
Correct |
95 ms |
131960 KB |
Output is correct |
25 |
Correct |
96 ms |
131196 KB |
Output is correct |
26 |
Correct |
98 ms |
131960 KB |
Output is correct |
27 |
Correct |
91 ms |
131960 KB |
Output is correct |
28 |
Correct |
84 ms |
114936 KB |
Output is correct |
29 |
Correct |
97 ms |
131960 KB |
Output is correct |
30 |
Correct |
84 ms |
115832 KB |
Output is correct |
31 |
Correct |
97 ms |
131960 KB |
Output is correct |
32 |
Correct |
78 ms |
101880 KB |
Output is correct |
33 |
Correct |
97 ms |
131960 KB |
Output is correct |
34 |
Execution timed out |
2092 ms |
73760 KB |
Time limit exceeded |
35 |
Halted |
0 ms |
0 KB |
- |