#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 1000005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n;
int A[MAXN][2];
pi dp[MAXN][2]; // {position, A/B}
pi combi(pi A, pi B){
int st=min(A.first,B.first);
int en=max(A.second,B.second);
return make_pair(st,en);
}
bool in(int x, pi r){
return r.first <= x && x<=r.second;
}
vector<char>out;
void backtrack(pi cur, int val){
debug(cur.first,cur.second);
if(cur.second == 0)out.push_back('A');
else out.push_back('B');
if(cur.first == 1)return;
int nval=val-(cur.second == 0);
debug(A[cur.first-1][0],A[cur.first][cur.second],dp[cur.first-1][0].first,dp[cur.first-1][0].second,nval);
if(A[cur.first-1][0] <= A[cur.first][cur.second] && in(nval,dp[cur.first-1][0])){
pi ncur=make_pair(cur.first-1,0);
backtrack(ncur,nval);
} else {
//assert(A[cur.first-1][1] <= A[cur.first][cur.second] && in(nval,dp[cur.first-1][1]));
pi ncur=make_pair(cur.first-1,1);
backtrack(ncur,nval);
}
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(int i=1;i<=2*n;i++)cin>>A[i][0];
for(int i=1;i<=2*n;i++)cin>>A[i][1];
for(int i=1;i<=2*n;i++){
for(int j=0;j<=1;j++){
dp[i][j]={-1,-1};
}
}
dp[0][0]={0,0};
dp[0][1]={0,0};
for(int i=1;i<=2*n;i++){
for(int j=0;j<=1;j++){
for(int k=0;k<=1;k++){
if(A[i-1][k] <= A[i][j]){
if(dp[i][j].first == -1){
if(j==0)dp[i][j]=make_pair(dp[i-1][k].first+1,dp[i-1][k].second+1);
else dp[i][j]=dp[i-1][k];
} else{
if(dp[i-1][k].first==-1)continue;
if(j==0)dp[i][j]=combi(dp[i][j],make_pair(dp[i-1][k].first+1,dp[i-1][k].second+1));
else dp[i][j]=combi(dp[i][j],dp[i-1][k]);
}
}
}
}
debug(i,dp[i][0].first,dp[i][0].second);
debug(i,dp[i][1].first,dp[i][1].second);
}
if(in(n,dp[2*n][0])){
pi cur=make_pair(2*n,0);
backtrack(cur,n);
reverse(out.begin(),out.end());
for(auto x:out)cout<<x;
exit(0);
}
if(in(n,dp[2*n][1])){
pi cur=make_pair(2*n,1);
backtrack(cur,n);
reverse(out.begin(),out.end());
for(auto x:out)cout<<x;
exit(0);
}
cout<<-1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
