# 笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭，要么我就注定铸就辉煌。如果有一天，你发现我在平庸面前低了头，请向我开炮。”

### JOID1T1 Sol瞎写

posted on 2020-03-20 23:55:20 | under 题解 |

T2、3都不会，别骂了别骂了QAQ

using namespace std ;

#define Trump return Output(), 0

const int N = 1000010 ;

int n ;
int cnt ;
int res[N] ;
int ans[N] ;
int f[N][2] ;
int g[N][2] ;
int base[N][2] ;

void Output(){
for (int i = 1 ; i <= n ; ++ i)
printf("%c", (char)('A' + ans[i])) ;
}
int getsign(int x){
return x ? 1 : -1 ;
}
int main(){
cin >> n ; n *= 2 ;
for (int i = 0 ; i <= n ; ++ i)
g[i][0] = g[i][1] = -1000001 ;
for (int j = 0 ; j < 2 ; ++ j)
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i][j]) ;
f[n][0] = f[n][1] = 1 ; int p = n - 1 ;
for (int i = p ; i >= 1 ; -- i)
for (int j = 0 ; j <= 1 ; ++ j)
for (int k = 0 ; k <= 1 ; ++ k){
if (!f[i + 1][k]) continue ;
if (base[i][j] <= base[i + 1][k])
f[i][j] |= f[i + 1][k] ;
}
if (!(f[1][1] or f[1][0])) return puts("-1"), 0 ;
ans[++ cnt] = ((base[1][0] >= base[1][1]) and (f[1][1])) ? 1 : 0 ;
for (int i = 2 ; i <= n ; ++ i){
if (base[i][0] < base[i][1]){
++ cnt ; int q = cnt - 1 ;
ans[cnt] = (base[i - 1][ans[q]] > base[i][0]) ? 1 : 0 ;
}
else {
++ cnt ; int q = cnt - 1 ;
ans[cnt] = (base[i - 1][ans[q]] > base[i][1]) ? 0 : 1 ;
}
}
//for (int i = 1 ; i <= n ; ++ i) cout << ans[i] << " " ; puts("") ;
int t = 0, dif = 0 ; g[n][ans[n]] = 0 ;
for (int i = 1 ; i <= n ; ++ i) t += getsign(ans[i]) ;
if (!t) Trump ; g[n][!ans[n]] = 2 * getsign(!ans[n]) * getsign(t < 0) ;
for (int i = p ; i >= 1 ; -- i)
for (int j = 0 ; j <= 1 ; ++ j){
dif = (ans[i] ^ j) ? (2 * getsign(!ans[i]) * getsign(t < 0)) : 0 ;
for (int k = 0 ; k <= 1 ; ++ k){
if (g[i + 1][k] == -1000001) continue ;
if (base[i + 1][k] < base[i][j]) continue ;
if (base[i - 1][ans[i - 1]] > base[i][j]) continue ;
g[i][j] = max(g[i][j], g[i + 1][k] + dif) ;
}
}
cnt = 0 ; int pq ;
res[++ cnt] = pq = (bool)(g[1][1] > g[1][0])  ;
if (max(g[1][0], g[1][1]) < (getsign(t > 0) * t)) return puts("-1"), 0 ;
for (int i = 1 ; i < n ; ++ i){
dif = (ans[i] ^ pq) ? (2 * getsign(!ans[i]) * getsign(t < 0)) : 0 ;
for (int k = 0 ; k <= 1 ; ++ k){
if (base[i + 1][k] < base[i][pq]) continue ;
if (g[i + 1][k] + dif == g[i][pq]) { res[++ cnt] = pq = k ; break ; }
}
}
//for (int i = 1 ; i <= n ; ++ i) cout << res[i] << " " ; puts("") ;
for (int i = 1 ; i <= n ; ++ i)
if (g[i][res[i]] == (getsign(t > 0) * t)){
for (int j = i ; j <= n ; ++ j) ans[j] = res[j] ;
Trump ;
}
Trump ;
}