#include <bits/stdc++.h>
#define ll int
#define MAXN 1000005
#define llinf 1e9
using namespace std;
ll a[2][MAXN],dp[2][MAXN][2];
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n;
cin >> n;
for (ll i=0;i<2;i++)
{
for (ll j=1;j<=2*n;j++)
cin >> a[i][j];
}
dp[0][1][0]=dp[0][1][1]=1;
dp[1][1][0]=dp[1][1][1]=0;
for (ll i=2;i<=2*n;i++)
{
dp[0][i][0]=dp[1][i][0]=llinf;
dp[0][i][1]=dp[1][i][1]=-llinf;
for (ll j=0;j<2;j++)
{
if (a[0][i]>=a[j][i-1])
{
dp[0][i][0]=min(dp[0][i][0],dp[j][i-1][0]+1);
dp[0][i][1]=max(dp[0][i][1],dp[j][i-1][1]+1);
}
if (a[1][i]>=a[j][i-1])
{
dp[1][i][0]=min(dp[1][i][0],dp[j][i-1][0]);
dp[1][i][1]=max(dp[1][i][1],dp[j][i-1][1]);
}
}
}
if ((dp[0][2*n][0]>n || dp[0][2*n][1]<n) && (dp[1][2*n][0]>n || dp[1][2*n][1]<n))
{
cout << -1;
return 0;
}
ll val=n,pos=2*n+1,i=1;
a[0][pos]=a[1][pos]=llinf;
string ans="";
while (pos>1)
{
val-=(1-i);
i=dp[0][pos-1][0]<=val && dp[0][pos-1][1]>=val && a[0][pos-1]<=a[i][pos]?0 : 1;
ans+=(i?"B" : "A");
pos--;
}
reverse(ans.begin(),ans.end());
cout << ans;
return 0;
}
# |
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 |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
468 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 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 |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
468 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
194 ms |
23404 KB |
Output is correct |
35 |
Correct |
204 ms |
24016 KB |
Output is correct |
36 |
Correct |
217 ms |
41296 KB |
Output is correct |
37 |
Correct |
222 ms |
42108 KB |
Output is correct |
38 |
Correct |
203 ms |
42208 KB |
Output is correct |
39 |
Correct |
198 ms |
41492 KB |
Output is correct |
40 |
Correct |
219 ms |
44768 KB |
Output is correct |
41 |
Correct |
194 ms |
42452 KB |
Output is correct |
42 |
Correct |
212 ms |
43784 KB |
Output is correct |
43 |
Correct |
223 ms |
45252 KB |
Output is correct |
44 |
Correct |
223 ms |
45252 KB |
Output is correct |
45 |
Correct |
233 ms |
45260 KB |
Output is correct |
46 |
Correct |
225 ms |
45232 KB |
Output is correct |
47 |
Correct |
245 ms |
44308 KB |
Output is correct |
48 |
Correct |
215 ms |
44100 KB |
Output is correct |
49 |
Correct |
220 ms |
45000 KB |
Output is correct |
50 |
Correct |
228 ms |
44440 KB |
Output is correct |
51 |
Correct |
237 ms |
44460 KB |
Output is correct |
52 |
Correct |
173 ms |
33512 KB |
Output is correct |
53 |
Correct |
152 ms |
33548 KB |
Output is correct |
54 |
Correct |
138 ms |
33468 KB |
Output is correct |
55 |
Correct |
134 ms |
33220 KB |
Output is correct |
56 |
Correct |
228 ms |
45480 KB |
Output is correct |
57 |
Correct |
180 ms |
40464 KB |
Output is correct |
58 |
Correct |
194 ms |
40380 KB |
Output is correct |
59 |
Correct |
180 ms |
40492 KB |
Output is correct |
60 |
Correct |
176 ms |
38552 KB |
Output is correct |
61 |
Correct |
190 ms |
40904 KB |
Output is correct |
62 |
Correct |
246 ms |
40372 KB |
Output is correct |
63 |
Correct |
183 ms |
40896 KB |
Output is correct |
64 |
Correct |
187 ms |
39536 KB |
Output is correct |
65 |
Correct |
194 ms |
40908 KB |
Output is correct |