This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
const int INF=1e9;
struct itv{
int l,r;
};
itv operator+(itv a,itv b){
return {min(a.l,b.l),max(a.r,b.r)};
}
int N;
int A[1000001],B[1000001];
itv DP[1000001][2];
string Ans;
itv dp(int i,int j){
itv &ret=DP[i][j];
if (ret.l!=-1||ret.r!=-1)
return ret;
ret={INF,-1};
int tmp=(j?B[i]:A[i]);
if (A[i-1]<=tmp&&(dp(i-1,0).l!=INF||dp(i-1,0).r!=-1))
ret=ret+dp(i-1,0);
if (B[i-1]<=tmp&&(dp(i-1,1).l!=INF||dp(i-1,1).r!=-1))
ret=ret+dp(i-1,1);
if (ret.l==INF&&ret.r==-1)
return ret;
if (!j){
ret.l++;
ret.r++;
}
return ret;
}
bool f(itv a,int x){
return (a.l<=x&&x<=a.r);
}
void solve(int i,int j,int k){
if (!i)
return;
if (k){
Ans+='B';
if (A[i-1]<=B[i]&&f(dp(i-1,0),j))
solve(i-1,j,0);
else
solve(i-1,j,1);
}
else{
Ans+='A';
if (A[i-1]<=A[i]&&f(dp(i-1,0),j-1))
solve(i-1,j-1,0);
else
solve(i-1,j-1,1);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>N;
for (int i=1; i<=2*N; i++)
DP[i][0]=DP[i][1]={-1,-1};
for (int i=1; i<=2*N; i++)
cin>>A[i];
for (int i=1; i<=2*N; i++)
cin>>B[i];
if (f(dp(N*2,0),N)){
solve(N*2,N,0);
reverse(all(Ans));
cout<<Ans;
return 0;
}
if (f(dp(N*2,1),N)){
solve(N*2,N,1);
reverse(all(Ans));
cout<<Ans;
return 0;
}
cout<<"-1";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |