#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=2e3+5;
int a[N*2],b[N*2],dp[N*2][N][2];
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n*2;i++)cin>>a[i];
for(int i=1;i<=n*2;i++)cin>>b[i];
dp[0][0][0]=1;
for(int i=1;i<=n*2;i++){
for(int j=0;j<=min(i,n);j++){
if(a[i]>=a[i-1]){
dp[i][j][0]=dp[i-1][j][0];
}
if(a[i]>=b[i-1] && !dp[i][j][0]){
dp[i][j][0]=dp[i-1][j][1];
}
if(j-1>=0){
if(b[i]>=a[i-1]){
dp[i][j][1]=dp[i-1][j-1][0];
}
if(b[i]>=b[i-1] && !dp[i][j][1]){
dp[i][j][1]=dp[i-1][j-1][1];
}
}
}
}
int x=n*2,y=n,z=-1;
string res="";
if(dp[n*2][n][1]==1)z=1;
if(dp[n*2][n][0]==1)z=0;
if(z==-1){
cout<<-1<<"\n";
return 0;
}
while(x>=1){
if(z==1){
res+='B';
if(b[x]>=a[x-1] && dp[x-1][y-1][0])z=0;
else z=1;
y--;
}
else{
if(a[x]>=a[x-1] && dp[x-1][y][0])z=0;
else z=1;
res+='A';
}
x--;
}
reverse(all(res));
cout<<res<<"\n";
}
/*
3
0 9
8 1
13 7
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
56 ms |
107512 KB |
Output is correct |
6 |
Correct |
30 ms |
104028 KB |
Output is correct |
7 |
Correct |
28 ms |
85852 KB |
Output is correct |
8 |
Correct |
33 ms |
109136 KB |
Output is correct |
9 |
Correct |
35 ms |
100432 KB |
Output is correct |
10 |
Correct |
19 ms |
100948 KB |
Output is correct |
11 |
Correct |
35 ms |
103944 KB |
Output is correct |
12 |
Correct |
34 ms |
119636 KB |
Output is correct |
13 |
Correct |
35 ms |
124304 KB |
Output is correct |
14 |
Correct |
32 ms |
125780 KB |
Output is correct |
15 |
Correct |
37 ms |
119380 KB |
Output is correct |
16 |
Correct |
28 ms |
125784 KB |
Output is correct |
17 |
Correct |
35 ms |
119632 KB |
Output is correct |
18 |
Correct |
33 ms |
120400 KB |
Output is correct |
19 |
Correct |
31 ms |
117076 KB |
Output is correct |
20 |
Correct |
32 ms |
118620 KB |
Output is correct |
21 |
Correct |
35 ms |
116060 KB |
Output is correct |
22 |
Correct |
26 ms |
125776 KB |
Output is correct |
23 |
Correct |
27 ms |
125780 KB |
Output is correct |
24 |
Correct |
25 ms |
125776 KB |
Output is correct |
25 |
Correct |
25 ms |
125628 KB |
Output is correct |
26 |
Correct |
25 ms |
125980 KB |
Output is correct |
27 |
Correct |
24 ms |
125788 KB |
Output is correct |
28 |
Correct |
24 ms |
112980 KB |
Output is correct |
29 |
Correct |
27 ms |
125268 KB |
Output is correct |
30 |
Correct |
26 ms |
111700 KB |
Output is correct |
31 |
Correct |
28 ms |
125788 KB |
Output is correct |
32 |
Correct |
22 ms |
107100 KB |
Output is correct |
33 |
Correct |
27 ms |
125968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
56 ms |
107512 KB |
Output is correct |
6 |
Correct |
30 ms |
104028 KB |
Output is correct |
7 |
Correct |
28 ms |
85852 KB |
Output is correct |
8 |
Correct |
33 ms |
109136 KB |
Output is correct |
9 |
Correct |
35 ms |
100432 KB |
Output is correct |
10 |
Correct |
19 ms |
100948 KB |
Output is correct |
11 |
Correct |
35 ms |
103944 KB |
Output is correct |
12 |
Correct |
34 ms |
119636 KB |
Output is correct |
13 |
Correct |
35 ms |
124304 KB |
Output is correct |
14 |
Correct |
32 ms |
125780 KB |
Output is correct |
15 |
Correct |
37 ms |
119380 KB |
Output is correct |
16 |
Correct |
28 ms |
125784 KB |
Output is correct |
17 |
Correct |
35 ms |
119632 KB |
Output is correct |
18 |
Correct |
33 ms |
120400 KB |
Output is correct |
19 |
Correct |
31 ms |
117076 KB |
Output is correct |
20 |
Correct |
32 ms |
118620 KB |
Output is correct |
21 |
Correct |
35 ms |
116060 KB |
Output is correct |
22 |
Correct |
26 ms |
125776 KB |
Output is correct |
23 |
Correct |
27 ms |
125780 KB |
Output is correct |
24 |
Correct |
25 ms |
125776 KB |
Output is correct |
25 |
Correct |
25 ms |
125628 KB |
Output is correct |
26 |
Correct |
25 ms |
125980 KB |
Output is correct |
27 |
Correct |
24 ms |
125788 KB |
Output is correct |
28 |
Correct |
24 ms |
112980 KB |
Output is correct |
29 |
Correct |
27 ms |
125268 KB |
Output is correct |
30 |
Correct |
26 ms |
111700 KB |
Output is correct |
31 |
Correct |
28 ms |
125788 KB |
Output is correct |
32 |
Correct |
22 ms |
107100 KB |
Output is correct |
33 |
Correct |
27 ms |
125968 KB |
Output is correct |
34 |
Runtime error |
4 ms |
604 KB |
Execution killed with signal 11 |
35 |
Halted |
0 ms |
0 KB |
- |