#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2001;
int prec[MAXN * 2][MAXN][2];
int A[MAXN * 2];
int B[MAXN * 2];
int N;
void dp(int posActu , int score , int iEtage)
{
//cout<<posActu<<" "<<score<<" "<<iEtage<<endl;
if (posActu == 2 * N -1)
{
return;
}
if (iEtage == 0)
{
if (score < N && prec[posActu + 1][score + 1][0] == -1 && A[posActu] <= A[posActu + 1])
{
// cout<<"QergqreGQ"<<endl;
prec[posActu + 1][score + 1][0] = 1;
dp(posActu + 1 , score + 1 , 0);
}
if (prec[posActu + 1][score][1] == -1 && A[posActu] <= B[posActu + 1])
{
prec[posActu + 1][score][1] = 2;
dp(posActu + 1 , score , 1);
}
}
else
{
if (score < N && prec[posActu + 1][score + 1][0] == -1 && B[posActu] <= A[posActu + 1])
{
// cout<<"QeroogqreGQ"<<endl;
prec[posActu + 1][score + 1][0] = 2;
dp(posActu + 1 , score + 1 , 0);
}
if (prec[posActu + 1][score][1] == -1 && B[posActu] <= B[posActu + 1])
{
prec[posActu + 1][score][1] = 1;
dp(posActu + 1 , score , 1);
}
}
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 0 ; i < N * 2 ; i++)
{
cin >> A[i];
}
for (int i = 0 ; i < N * 2 ; i++)
{
cin >> B[i];
}
for (int i = 0 ; i < MAXN * 2 ; i++)
{
for (int j = 0 ; j < MAXN ; j++)
{
prec[i][j][0] = prec[i][j][1] = -1;
}
}
dp(0 , 1 , 0);
dp(0 , 0 , 1);
int posActu = 0;
if (prec[2 * N - 1][N][0] != -1)
{
posActu = 0;
}
else if (prec[2* N - 1][N][1] != -1)
{
posActu = 1;
}
else
{
cout<<-1<<endl;
exit(0);
}
vector <int> sol;
int scoreActu = N;
for (int i = 0 ; i < 2 * N ; i++)
{
//cout<<i<<" e"<<posActu<<" "<<scoreActu<<" "<<prec[2 * N -1 - i][scoreActu][posActu]<<" "<<2 * N - 1 - i<<endl;
sol.push_back(posActu);
if (i < 2 * N - 1)
{
int pp = posActu;
if (prec[2 * N - 1 - i][scoreActu][posActu] == 2)
{
// cout<<"a"<<endl;
posActu = 1 - posActu;
}
scoreActu -= (pp == 0);
}
}
for (int i = 2 * N -1 ; i >= 0 ; i--)
{
if (sol[i] == 0) cout<<"A";
else cout<<"B";
}
cout<<endl;
/*for (int k = 0 ; k < 2 ; k++)
{
for (int i = 0 ; i < 2 * N ; i++)
{
for (int j = 0 ; j <= N ; j++)
{
cout<<prec[i][j][k]<<" ";
}
cout<<endl;
}
cout<<endl;
}*/
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
125692 KB |
Output is correct |
2 |
Correct |
65 ms |
125688 KB |
Output is correct |
3 |
Correct |
63 ms |
125688 KB |
Output is correct |
4 |
Correct |
63 ms |
125688 KB |
Output is correct |
5 |
Correct |
64 ms |
125864 KB |
Output is correct |
6 |
Correct |
66 ms |
125944 KB |
Output is correct |
7 |
Correct |
63 ms |
125944 KB |
Output is correct |
8 |
Correct |
129 ms |
125956 KB |
Output is correct |
9 |
Correct |
124 ms |
125944 KB |
Output is correct |
10 |
Correct |
140 ms |
125944 KB |
Output is correct |
11 |
Correct |
65 ms |
126072 KB |
Output is correct |
12 |
Correct |
65 ms |
125944 KB |
Output is correct |
13 |
Correct |
65 ms |
125944 KB |
Output is correct |
14 |
Correct |
154 ms |
125944 KB |
Output is correct |
15 |
Correct |
147 ms |
125976 KB |
Output is correct |
16 |
Correct |
119 ms |
125956 KB |
Output is correct |
17 |
Correct |
130 ms |
125980 KB |
Output is correct |
18 |
Correct |
65 ms |
125944 KB |
Output is correct |
19 |
Correct |
66 ms |
125976 KB |
Output is correct |
20 |
Correct |
68 ms |
125944 KB |
Output is correct |
21 |
Correct |
67 ms |
125948 KB |
Output is correct |
22 |
Correct |
170 ms |
126048 KB |
Output is correct |
23 |
Correct |
141 ms |
125944 KB |
Output is correct |
24 |
Correct |
171 ms |
125980 KB |
Output is correct |
25 |
Correct |
139 ms |
125944 KB |
Output is correct |
26 |
Correct |
135 ms |
125976 KB |
Output is correct |
27 |
Correct |
136 ms |
125948 KB |
Output is correct |
28 |
Correct |
103 ms |
126176 KB |
Output is correct |
29 |
Correct |
115 ms |
125944 KB |
Output is correct |
30 |
Correct |
105 ms |
125944 KB |
Output is correct |
31 |
Correct |
111 ms |
125944 KB |
Output is correct |
32 |
Correct |
111 ms |
125920 KB |
Output is correct |
33 |
Correct |
106 ms |
125920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
125692 KB |
Output is correct |
2 |
Correct |
65 ms |
125688 KB |
Output is correct |
3 |
Correct |
63 ms |
125688 KB |
Output is correct |
4 |
Correct |
63 ms |
125688 KB |
Output is correct |
5 |
Correct |
64 ms |
125864 KB |
Output is correct |
6 |
Correct |
66 ms |
125944 KB |
Output is correct |
7 |
Correct |
63 ms |
125944 KB |
Output is correct |
8 |
Correct |
129 ms |
125956 KB |
Output is correct |
9 |
Correct |
124 ms |
125944 KB |
Output is correct |
10 |
Correct |
140 ms |
125944 KB |
Output is correct |
11 |
Correct |
65 ms |
126072 KB |
Output is correct |
12 |
Correct |
65 ms |
125944 KB |
Output is correct |
13 |
Correct |
65 ms |
125944 KB |
Output is correct |
14 |
Correct |
154 ms |
125944 KB |
Output is correct |
15 |
Correct |
147 ms |
125976 KB |
Output is correct |
16 |
Correct |
119 ms |
125956 KB |
Output is correct |
17 |
Correct |
130 ms |
125980 KB |
Output is correct |
18 |
Correct |
65 ms |
125944 KB |
Output is correct |
19 |
Correct |
66 ms |
125976 KB |
Output is correct |
20 |
Correct |
68 ms |
125944 KB |
Output is correct |
21 |
Correct |
67 ms |
125948 KB |
Output is correct |
22 |
Correct |
170 ms |
126048 KB |
Output is correct |
23 |
Correct |
141 ms |
125944 KB |
Output is correct |
24 |
Correct |
171 ms |
125980 KB |
Output is correct |
25 |
Correct |
139 ms |
125944 KB |
Output is correct |
26 |
Correct |
135 ms |
125976 KB |
Output is correct |
27 |
Correct |
136 ms |
125948 KB |
Output is correct |
28 |
Correct |
103 ms |
126176 KB |
Output is correct |
29 |
Correct |
115 ms |
125944 KB |
Output is correct |
30 |
Correct |
105 ms |
125944 KB |
Output is correct |
31 |
Correct |
111 ms |
125944 KB |
Output is correct |
32 |
Correct |
111 ms |
125920 KB |
Output is correct |
33 |
Correct |
106 ms |
125920 KB |
Output is correct |
34 |
Runtime error |
477 ms |
273472 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
35 |
Halted |
0 ms |
0 KB |
- |