Submission #1331262

#TimeUsernameProblemLanguageResultExecution timeMemory
1331262MrAndriaBuilding 4 (JOI20_building4)C++20
0 / 100
1 ms580 KiB
/*
¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
¦¦¦_¯¦¦¦¦¦¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦_¯_¯_¯_¯_¯_¯¦¦¦¦¦¦¦_¯_¯_¯_¯_¯¦¦¦¦¦_¯¦¦¦¦¦¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦_¯_¯_¯_¯¦¦¦¦¦¦¦_¯_¯_¯_¯_¯_¯¦¦¦¦¦¦¦_¯_¯_¯¦¦¦¦¦_¯_¯_¯_¯_¯¦¦¦
¦¦¦_¯_¯_¯_¯_¯_¯_¯_¯_¯¦¦¦¦¦_¯¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯_¯_¯_¯_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦_¯_¯¦¦¦¦¦_¯¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦
¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦
¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦
¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯_¯_¯_¯_¯_¯¦¦¦¦¦¦¦_¯_¯_¯_¯_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯_¯_¯_¯_¯_¯¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦_¯_¯_¯_¯_¯¦¦¦
¦¦¦_¯¦¦¦¦¦¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦
¦¦¦_¯¦¦¦¦¦¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦
¦¦¦_¯¦¦¦¦¦¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯_¯_¯_¯_¯¦¦¦¦¦_¯¦¦¦¦_¯_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦
¦¦¦_¯¦¦¦¦¦¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯_¯_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦¦¦_¯¦¦¦¦¦¦¦¦¦¦¦¦¦¦_¯¦¦¦¦¦_¯_¯_¯_¯¦¦¦¦¦¦¦_¯¦¦¦¦¦¦_¯_¯_¯¦¦¦¦¦_¯_¯_¯¦¦¦¦¦_¯¦¦¦¦¦¦_¯¦¦¦
¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
*/
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
//#define int long long
int l,r,n,t,m,mid,ans,sum,sum1,sum2,sum0,k,a[1000005][3];
vector <int> v,v1;
map <int,int> mp;
string s,s1;
bool b1;
pair <int,int> dp[500005][3];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<=1;i++){
        for(int j=1;j<=2*n;j++){
            cin>>a[j][i];
        }
    }
    for(int i=1;i<=2*n;i++){
        dp[i][0]=make_pair(2*n+1,2*n+1);
        dp[i][1]=make_pair(2*n+1,2*n+1);
        if(a[i-1][0]<=a[i][0]){
            dp[i][0].ff=min(dp[i][0].ff,dp[i-1][0].ff+1);
            dp[i][0].ss=max(dp[i][0].ss,dp[i-1][0].ss+1);
        }
        if(a[i-1][1]<=a[i][0]){
            dp[i][0].ff=min(dp[i][0].ff,dp[i-1][1].ff+1);
            dp[i][0].ss=max(dp[i][0].ss,dp[i-1][1].ss+1);
        }
        if(a[i-1][0]<=a[i][1]){
            dp[i][1].ff=min(dp[i][1].ff,dp[i-1][0].ff);
            dp[i][1].ss=max(dp[i][1].ss,dp[i-1][0].ss);
        }
        if(a[i-1][1]<=a[i][1]){
            dp[i][1].ff=min(dp[i][1].ff,dp[i-1][1].ff);
            dp[i][1].ss=max(dp[i][1].ss,dp[i-1][1].ss);
        }
    }
    if((dp[2*n][0].ff<=n and n<=dp[2*n][0].ss) or (dp[2*n][1].ff<=n and n<=dp[2*n][1].ss)){

    }else{
        cout<<-1<<endl;
        return 0;
    }
    int curra=0;
    int pre=INT_MAX;
    for(int i=2*n;i>=1;i--){
        if(dp[i][0].ff<=n-curra and n-curra<=dp[i][0].ss and a[i][0]<=pre){
            curra++;
            pre=a[i][0];
            s.pb('A');
        }else{
            s.pb('B');
            pre=a[i][1];

        }
    }
    reverse(s.begin(),s.end());
    cout<<s<<endl;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...