#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
ll n, A[1000001], B[1000001];
bool dp[4001][2001][2];
void p(bool zf){
if(zf==0)cout << 'A';
else cout << 'B';
return ;
}
void dfs(ll xf, ll yf, ll zf){
if(xf==0){
p(zf);
return;
}
if(zf==0){
if((A[xf]>=A[xf-1]&&dp[xf-1][yf][0])){
dfs(xf-1, yf, 0);
}
else if((A[xf]>=B[xf-1]&&dp[xf-1][yf][1])){
dfs(xf-1, yf, 1);
}
}
else{
if((B[xf]>=A[xf-1]&&dp[xf-1][yf-1][0])){
dfs(xf-1, yf-1, 0);
}
else if((B[xf]>=B[xf-1]&&dp[xf-1][yf-1][1])){
dfs(xf-1, yf-1, 1);
}
}
p(zf);
return ;
}
int main(){
cin >> n;
for(int i=0; i<2*n; i++){
cin >> A[i];
}
for(int i=0; i<2*n; i++){
cin >> B[i];
}
dp[0][0][0]=1;
dp[0][1][1]=1;
for(int i=1; i<2*n; i++){
for(int t=0; t<=n; t++){
if(t>0){
dp[i][t][1]=((B[i]>=A[i-1]&&dp[i-1][t-1][0])||(B[i]>=B[i-1]&&dp[i-1][t-1][1]));
}
dp[i][t][0]=((A[i]>=A[i-1]&&dp[i-1][t][0])||(A[i]>=B[i-1]&&dp[i-1][t][1]));
}
}
if(dp[2*n-1][n][0]){
dfs(2*n-1, n, 0);
}
else if(dp[2*n-1][n][1]){
dfs(2*n-1, n, 1);
}
else{
cout << -1;
}
return 0;
}
/*
3
2 5 4 9 15 11
6 7 6 8 12 14
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
29 ms |
14788 KB |
Output is correct |
6 |
Correct |
30 ms |
14588 KB |
Output is correct |
7 |
Correct |
22 ms |
13004 KB |
Output is correct |
8 |
Correct |
23 ms |
14028 KB |
Output is correct |
9 |
Correct |
22 ms |
14276 KB |
Output is correct |
10 |
Correct |
17 ms |
12792 KB |
Output is correct |
11 |
Correct |
24 ms |
15252 KB |
Output is correct |
12 |
Correct |
31 ms |
16212 KB |
Output is correct |
13 |
Correct |
30 ms |
16204 KB |
Output is correct |
14 |
Correct |
30 ms |
16104 KB |
Output is correct |
15 |
Correct |
33 ms |
16208 KB |
Output is correct |
16 |
Correct |
34 ms |
15980 KB |
Output is correct |
17 |
Correct |
30 ms |
16196 KB |
Output is correct |
18 |
Correct |
31 ms |
16256 KB |
Output is correct |
19 |
Correct |
33 ms |
16224 KB |
Output is correct |
20 |
Correct |
33 ms |
16184 KB |
Output is correct |
21 |
Correct |
29 ms |
16068 KB |
Output is correct |
22 |
Correct |
28 ms |
16072 KB |
Output is correct |
23 |
Correct |
25 ms |
16068 KB |
Output is correct |
24 |
Correct |
24 ms |
16152 KB |
Output is correct |
25 |
Correct |
30 ms |
16064 KB |
Output is correct |
26 |
Correct |
26 ms |
16064 KB |
Output is correct |
27 |
Correct |
22 ms |
16100 KB |
Output is correct |
28 |
Correct |
23 ms |
14516 KB |
Output is correct |
29 |
Correct |
28 ms |
16168 KB |
Output is correct |
30 |
Correct |
25 ms |
14452 KB |
Output is correct |
31 |
Correct |
36 ms |
16316 KB |
Output is correct |
32 |
Correct |
26 ms |
13612 KB |
Output is correct |
33 |
Correct |
32 ms |
16200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
29 ms |
14788 KB |
Output is correct |
6 |
Correct |
30 ms |
14588 KB |
Output is correct |
7 |
Correct |
22 ms |
13004 KB |
Output is correct |
8 |
Correct |
23 ms |
14028 KB |
Output is correct |
9 |
Correct |
22 ms |
14276 KB |
Output is correct |
10 |
Correct |
17 ms |
12792 KB |
Output is correct |
11 |
Correct |
24 ms |
15252 KB |
Output is correct |
12 |
Correct |
31 ms |
16212 KB |
Output is correct |
13 |
Correct |
30 ms |
16204 KB |
Output is correct |
14 |
Correct |
30 ms |
16104 KB |
Output is correct |
15 |
Correct |
33 ms |
16208 KB |
Output is correct |
16 |
Correct |
34 ms |
15980 KB |
Output is correct |
17 |
Correct |
30 ms |
16196 KB |
Output is correct |
18 |
Correct |
31 ms |
16256 KB |
Output is correct |
19 |
Correct |
33 ms |
16224 KB |
Output is correct |
20 |
Correct |
33 ms |
16184 KB |
Output is correct |
21 |
Correct |
29 ms |
16068 KB |
Output is correct |
22 |
Correct |
28 ms |
16072 KB |
Output is correct |
23 |
Correct |
25 ms |
16068 KB |
Output is correct |
24 |
Correct |
24 ms |
16152 KB |
Output is correct |
25 |
Correct |
30 ms |
16064 KB |
Output is correct |
26 |
Correct |
26 ms |
16064 KB |
Output is correct |
27 |
Correct |
22 ms |
16100 KB |
Output is correct |
28 |
Correct |
23 ms |
14516 KB |
Output is correct |
29 |
Correct |
28 ms |
16168 KB |
Output is correct |
30 |
Correct |
25 ms |
14452 KB |
Output is correct |
31 |
Correct |
36 ms |
16316 KB |
Output is correct |
32 |
Correct |
26 ms |
13612 KB |
Output is correct |
33 |
Correct |
32 ms |
16200 KB |
Output is correct |
34 |
Execution timed out |
2015 ms |
36884 KB |
Time limit exceeded |
35 |
Halted |
0 ms |
0 KB |
- |