이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |