#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;
int ar[1000006];
int br[1000006];
pair<int,int>dp[2][1000006];
int ans[1000006];
bool intersect(pair<int,int>a,pair<int,int>b){
if(a.X>=b.Y+2){return 0;}
if(b.X>=a.Y+2){return 0;}
return 1;
}
signed main(){
cin>>n;n*=2;
for(int i=1;i<=n;i++){
cin>>ar[i];
}
for(int i=1;i<=n;i++){
cin>>br[i];
}
dp[0][1]={0,0};
dp[1][1]={1,1};
for(int i=2;i<=n;i++){
pair<int,int>a={1e9,-1e9};pair<int,int>b={1e9,-1e9};
if(ar[i]>=ar[i-1]){
a=dp[0][i-1];
}
if(ar[i]>=br[i-1]){
if(a.X<=1000000&&!intersect(a,dp[1][i-1])&&dp[1][i-1].first<=dp[1][i-1].second){return 0;}
a={min(dp[1][i-1].first,a.first),max(dp[1][i-1].second,a.second)};
}
if(br[i]>=ar[i-1]){
b=dp[0][i-1];
b.first++;b.second++;
}
if(br[i]>=br[i-1]){
if(b.X<=1000000&&!intersect(b,{dp[1][i-1].X+1,dp[1][i-1].Y+1} )&&dp[1][i-1].first<=dp[1][i-1].second){return 0;}
b={min(dp[1][i-1].first+1,b.first),max(dp[1][i-1].second+1,b.second)};
}
// cout<<a.X<<" "<<a.Y<<" "<<b.X<<" "<<b.Y<<endl;
if(a.X<=1000000&&b.X<=1000000&&!intersect(a,b)){return 0;}
dp[1][i]=b;
dp[0][i]=a;
}
int bcnt=0;int lst=1e18;
for(int i=n;i>=1;i--){
if(br[i]<=lst&&n/2-bcnt>=dp[1][i].first&&n/2-bcnt<=dp[1][i].second){
ans[i]=1;
bcnt++;
lst=br[i];
}else{
if(ar[i]>lst){cout<<-1;return 0;}
ans[i]=0;
lst=ar[i];
}
}
if(bcnt!=n/2){cout<<-1;return 0;}
for(int i=1;i<=n;i++){
if(ans[i]==0){
cout<<"A";
}else{
cout<<"B";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
