#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define MAXN 1000007
int n ;
int a[ MAXN ][ 3 ] ;
int ans[ MAXN ] ;
pair < int , int > dp[ MAXN ][ 3 ] ;
void input ( ) {
cin >> n ;
n *= 2 ;
for ( int i = 1 ; i <= n ; ++ i ) {
cin >> a[ i ][ 1 ] ;
}
for ( int i = 1 ; i <= n ; ++ i ) {
cin >> a[ i ][ 2 ] ;
}
}
void solve ( ) {
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 1 ; j <= 2 ; ++ j ) {
dp[ i ][ j ] = { MAXN , -MAXN } ;
}
}
dp[ 1 ][ 1 ] = { 1 , 1 } ;
dp[ 1 ][ 2 ] = { 0 , 0 } ;
for ( int i = 2 ; i <= n ; ++ i ) {
for ( int j = 1 ; j <= 2 ; ++ j ) {
for ( int t = 1 ; t <= 2 ; ++ t ) {
if ( a[ i ][ j ] >= a[ i - 1 ][ t ] ) {
dp[ i ][ j ].first = min ( dp[ i ][ j ].first , dp[ i - 1 ][ t ].first + ( j == 1 ) ) ;
dp[ i ][ j ].second = max ( dp[ i ][ j ].second , dp[ i - 1 ][ t ].second + ( j == 1 ) ) ;
}
}
}
}
int sr = ( n / 2 ) ;
int x = n , y = -1 ;
if ( dp[ n ][ 1 ].first <= sr && sr <= dp[ n ][ 1 ].second ) { y = 1 ; }
if ( dp[ n ][ 2 ].first <= sr && sr <= dp[ n ][ 2 ].second ) { y = 2 ; }
if ( y == -1 ) {
cout << "-1\n" ;
return ;
}
ans[ x ] = y ;
while ( x > 1 ) {
sr -= ( y == 1 ) ;
if ( a[ x - 1 ][ 1 ] <= a[ x ][ y ] && dp[ x - 1 ][ 1 ].first <= sr && sr <= dp[ x - 1 ][ 1 ].second ) {
y = 1 ;
}
else {
y = 2 ;
}
-- x ;
ans[ x ] = y ;
}
for ( int i = 1 ; i <= n ; ++ i ) {
if ( ans[ i ] == 1 ) { cout << "A" ; }
else { cout << "B" ; }
}
cout << "\n" ;
}
int main ( ) {
//freopen ( "dictionary.in" , "r" , stdin ) ;
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ;
// cin >> t ;
while ( t -- ) {
input ( ) ;
solve ( ) ;
}
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
476 KB |
Output is correct |
10 |
Correct |
1 ms |
412 KB |
Output is correct |
11 |
Correct |
2 ms |
552 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
472 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
2 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 |
468 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 |
472 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
2 ms |
468 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
2 ms |
468 KB |
Output is correct |
32 |
Correct |
1 ms |
520 KB |
Output is correct |
33 |
Correct |
1 ms |
472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
476 KB |
Output is correct |
10 |
Correct |
1 ms |
412 KB |
Output is correct |
11 |
Correct |
2 ms |
552 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
472 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
2 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 |
468 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 |
472 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
2 ms |
468 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
2 ms |
468 KB |
Output is correct |
32 |
Correct |
1 ms |
520 KB |
Output is correct |
33 |
Correct |
1 ms |
472 KB |
Output is correct |
34 |
Correct |
220 ms |
53932 KB |
Output is correct |
35 |
Correct |
245 ms |
55444 KB |
Output is correct |
36 |
Correct |
239 ms |
54628 KB |
Output is correct |
37 |
Correct |
244 ms |
55612 KB |
Output is correct |
38 |
Correct |
222 ms |
55664 KB |
Output is correct |
39 |
Correct |
217 ms |
55036 KB |
Output is correct |
40 |
Correct |
240 ms |
59176 KB |
Output is correct |
41 |
Correct |
218 ms |
56088 KB |
Output is correct |
42 |
Correct |
260 ms |
57828 KB |
Output is correct |
43 |
Correct |
255 ms |
59792 KB |
Output is correct |
44 |
Correct |
251 ms |
59740 KB |
Output is correct |
45 |
Correct |
262 ms |
59852 KB |
Output is correct |
46 |
Correct |
241 ms |
59760 KB |
Output is correct |
47 |
Correct |
239 ms |
58904 KB |
Output is correct |
48 |
Correct |
244 ms |
58700 KB |
Output is correct |
49 |
Correct |
248 ms |
59492 KB |
Output is correct |
50 |
Correct |
252 ms |
59064 KB |
Output is correct |
51 |
Correct |
266 ms |
58968 KB |
Output is correct |
52 |
Correct |
181 ms |
48080 KB |
Output is correct |
53 |
Correct |
183 ms |
47988 KB |
Output is correct |
54 |
Correct |
168 ms |
48056 KB |
Output is correct |
55 |
Correct |
165 ms |
47680 KB |
Output is correct |
56 |
Correct |
247 ms |
60012 KB |
Output is correct |
57 |
Correct |
205 ms |
54756 KB |
Output is correct |
58 |
Correct |
199 ms |
54964 KB |
Output is correct |
59 |
Correct |
216 ms |
54912 KB |
Output is correct |
60 |
Correct |
199 ms |
52196 KB |
Output is correct |
61 |
Correct |
208 ms |
55384 KB |
Output is correct |
62 |
Correct |
216 ms |
54668 KB |
Output is correct |
63 |
Correct |
215 ms |
55432 KB |
Output is correct |
64 |
Correct |
215 ms |
53560 KB |
Output is correct |
65 |
Correct |
208 ms |
55456 KB |
Output is correct |