#include "bits/stdc++.h"
using namespace std;
#define mp make_pair
#define f first
#define s second
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define For(i,b) FOR(i,0,b)
#define trav(a,b) for(auto& a:b)
#define vi vector<int>
#define vpi vector<pi>
#define pb push_back
#define bk back()
#define ins insert
#define pi pair<int,int>
#define ll long long
#define sz(x) (int) x.size()
#define all(x) x.begin(),x.end()
#define nl '\n'
const int MX=1e6+10;
const int MX2=4e6+10;
int n,a[MX][2];
vector<vector<vi>> dp[MX];//hold val of hm A left
vector<vector<vpi>> dp2[MX];//hold val of hm A left
//dp[i][j][k][l]
// void dbg(){
// cerr<<endl;
// }
// template<class A,class... B> dbg(A a, B... b){
// cerr<<a;
// if(sizeof...(b))cerr<<", ";
// dbg(b...);
// }
struct DivC{
void go(int x,int l, int r){
dp[x]=vector<vector<vi>>(r-l+2,vector<vi>(2,vi(2,-1)));
dp2[x]=vector<vector<vpi>>(r-l+2,vector<vpi>(2,vpi(2,{-1,-1})));
if(l==r){
dp[x][1][0][0]=1;
dp[x][0][1][1]=0;
return;
}
if(l!=r){
int m=(l+r)/2;
go(x*2,l,m);
go(x*2+1,m+1,r);
For(i,r-l+2){//16nlog
For(t1,2)For(t2,2){
For(t3,2)For(t4,2){
For(k,i+1){
if(k<sz(dp[x*2]) && i-k<sz(dp[x*2+1])){
if(a[m][t3]<=a[m+1][t4]){
if(dp[x*2][k][t1][t3]!=-1 && dp[x*2+1][i-k][t4][t2]!=-1){
dp[x][i][t1][t2]=k;
dp2[x][i][t1][t2]={t3,t4};
break;
}
}
}
}
}
}
}
}
}
};
DivC dc;
string ret;
void go2(int x, int as, int l, int r){
if(sz(dp[x])==2){
ret+=(as?"A":"B");
} else {
int num=dp[x][as][l][r];
int t1=dp2[x][as][l][r].f;
int t2=dp2[x][as][l][r].s;
go2(x*2,num,l,t1);
go2(x*2+1,as-num,t2,r);
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n;
For(i,2*n)cin>>a[i][0];
For(i,2*n)cin>>a[i][1];
dc.go(1,0,2*n-1);
For(i,2)For(j,2){
// cout<<i<<" "<<j<<" "<<dp[1][n][i][j]<<nl;
if(dp[1][n][i][j]!=-1){
go2(1,n,i,j);
cout<<ret<<nl;
return 0;
}
}
cout<<-1<<nl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
47340 KB |
Output is correct |
2 |
Correct |
34 ms |
47288 KB |
Output is correct |
3 |
Correct |
30 ms |
47340 KB |
Output is correct |
4 |
Correct |
31 ms |
47340 KB |
Output is correct |
5 |
Correct |
418 ms |
64108 KB |
Output is correct |
6 |
Correct |
452 ms |
63596 KB |
Output is correct |
7 |
Correct |
378 ms |
61700 KB |
Output is correct |
8 |
Correct |
153 ms |
62700 KB |
Output is correct |
9 |
Correct |
383 ms |
63084 KB |
Output is correct |
10 |
Correct |
357 ms |
61380 KB |
Output is correct |
11 |
Correct |
463 ms |
64236 KB |
Output is correct |
12 |
Correct |
528 ms |
65516 KB |
Output is correct |
13 |
Correct |
545 ms |
65516 KB |
Output is correct |
14 |
Correct |
161 ms |
65388 KB |
Output is correct |
15 |
Correct |
525 ms |
65388 KB |
Output is correct |
16 |
Correct |
494 ms |
65516 KB |
Output is correct |
17 |
Correct |
472 ms |
65456 KB |
Output is correct |
18 |
Correct |
579 ms |
65524 KB |
Output is correct |
19 |
Correct |
535 ms |
65516 KB |
Output is correct |
20 |
Correct |
586 ms |
65388 KB |
Output is correct |
21 |
Correct |
571 ms |
65516 KB |
Output is correct |
22 |
Correct |
165 ms |
65388 KB |
Output is correct |
23 |
Correct |
458 ms |
65388 KB |
Output is correct |
24 |
Correct |
332 ms |
65516 KB |
Output is correct |
25 |
Correct |
534 ms |
65388 KB |
Output is correct |
26 |
Correct |
553 ms |
65364 KB |
Output is correct |
27 |
Correct |
585 ms |
65456 KB |
Output is correct |
28 |
Correct |
425 ms |
63340 KB |
Output is correct |
29 |
Correct |
564 ms |
65516 KB |
Output is correct |
30 |
Correct |
453 ms |
63596 KB |
Output is correct |
31 |
Correct |
538 ms |
65388 KB |
Output is correct |
32 |
Correct |
400 ms |
62316 KB |
Output is correct |
33 |
Correct |
566 ms |
65516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
47340 KB |
Output is correct |
2 |
Correct |
34 ms |
47288 KB |
Output is correct |
3 |
Correct |
30 ms |
47340 KB |
Output is correct |
4 |
Correct |
31 ms |
47340 KB |
Output is correct |
5 |
Correct |
418 ms |
64108 KB |
Output is correct |
6 |
Correct |
452 ms |
63596 KB |
Output is correct |
7 |
Correct |
378 ms |
61700 KB |
Output is correct |
8 |
Correct |
153 ms |
62700 KB |
Output is correct |
9 |
Correct |
383 ms |
63084 KB |
Output is correct |
10 |
Correct |
357 ms |
61380 KB |
Output is correct |
11 |
Correct |
463 ms |
64236 KB |
Output is correct |
12 |
Correct |
528 ms |
65516 KB |
Output is correct |
13 |
Correct |
545 ms |
65516 KB |
Output is correct |
14 |
Correct |
161 ms |
65388 KB |
Output is correct |
15 |
Correct |
525 ms |
65388 KB |
Output is correct |
16 |
Correct |
494 ms |
65516 KB |
Output is correct |
17 |
Correct |
472 ms |
65456 KB |
Output is correct |
18 |
Correct |
579 ms |
65524 KB |
Output is correct |
19 |
Correct |
535 ms |
65516 KB |
Output is correct |
20 |
Correct |
586 ms |
65388 KB |
Output is correct |
21 |
Correct |
571 ms |
65516 KB |
Output is correct |
22 |
Correct |
165 ms |
65388 KB |
Output is correct |
23 |
Correct |
458 ms |
65388 KB |
Output is correct |
24 |
Correct |
332 ms |
65516 KB |
Output is correct |
25 |
Correct |
534 ms |
65388 KB |
Output is correct |
26 |
Correct |
553 ms |
65364 KB |
Output is correct |
27 |
Correct |
585 ms |
65456 KB |
Output is correct |
28 |
Correct |
425 ms |
63340 KB |
Output is correct |
29 |
Correct |
564 ms |
65516 KB |
Output is correct |
30 |
Correct |
453 ms |
63596 KB |
Output is correct |
31 |
Correct |
538 ms |
65388 KB |
Output is correct |
32 |
Correct |
400 ms |
62316 KB |
Output is correct |
33 |
Correct |
566 ms |
65516 KB |
Output is correct |
34 |
Runtime error |
788 ms |
524292 KB |
Execution killed with signal 9 |
35 |
Halted |
0 ms |
0 KB |
- |