#include<bits/stdc++.h>
#define MAXN 500007
using namespace std;
const int inf=1e9;
int n,a[MAXN],b[MAXN],cnt,p[MAXN],l,r;
int dp[MAXN][2],dp2[MAXN][2];
bool li[MAXN][2],li2[MAXN][2];
vector< deque<int> > w;
string sol,sol2;
int ff(int pos,int last){
if(pos==n+1)return 0;
if(li[pos][last])return dp[pos][last];
li[pos][last]=true;
dp[pos][last]=-inf;
int x=0;
if(last==0)x=a[pos-1];
else x=b[pos-1];
if(a[pos]>=x){
dp[pos][last]=max(dp[pos][last],ff(pos+1,0)+1);
}
if(b[pos]>=x){
dp[pos][last]=max(dp[pos][last],ff(pos+1,1));
}
return dp[pos][last];
}
int ff2(int pos,int last){
if(pos==n+1)return 0;
if(li2[pos][last])return dp2[pos][last];
li2[pos][last]=true;
dp2[pos][last]=-inf;
int x=0;
if(last==0)x=a[pos-1];
else x=b[pos-1];
if(a[pos]>=x){
dp2[pos][last]=max(dp2[pos][last],ff2(pos+1,0));
}
if(b[pos]>=x){
dp2[pos][last]=max(dp2[pos][last],ff2(pos+1,1)+1);
}
return dp2[pos][last];
}
void solve(int pos,int last){
if(pos==n+1)return;
int x;
if(last==0)x=a[pos-1];
else x=b[pos-1];
if(a[pos]>=x and ff(pos,last)==ff(pos+1,0)+1){
sol+="A"; solve(pos+1,0); return;
}else{
sol+="B"; solve(pos+1,1); return;
}
}
void solve2(int pos,int last){
if(pos==n+1)return;
int x;
if(last==0)x=a[pos-1];
else x=b[pos-1];
if(b[pos]>=x and ff2(pos,last)==ff2(pos+1,1)+1){
sol2+="B"; solve2(pos+1,1); return;
}else{
sol2+="A"; solve2(pos+1,0); return;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
n*=2;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
if(ff(1,0)<0 or ff(1,0)<n/2 or ff2(1,0)<n/2){
cout<<"-1\n";
return 0;
}
cnt=ff(1,0);
solve(1,0); solve2(1,0);
for(int i=0;i<sol.size();i++){
if(sol[i]=='A')p[i+1]=a[i+1];
else p[i+1]=b[i+1];
}
p[n+1]=inf;
for(int i=0;i<sol.size();i++){
if(sol[i]=='A' and sol2[i]=='B'){
w.back().push_back(i);
}else{
w.push_back({});
}
}
while(cnt>n/2){
while(w.back().empty())w.pop_back();
l=w.back().front();
r=w.back().back();
if(b[l+1]>=p[l] and b[l+1]<=p[l+2]){
sol[l]='B'; p[l+1]=b[l+1];
w.back().pop_front();
}else{
sol[r]='B'; p[r+1]=b[r+1];
w.back().pop_back();
}
cnt--;
}
cout<<sol<<"\n";
return 0;
}
Compilation message
building4.cpp: In function 'int main()':
building4.cpp:108:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=0;i<sol.size();i++){
| ~^~~~~~~~~~~
building4.cpp:114:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i=0;i<sol.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
17240 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
17240 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
