Submission #1256066

#TimeUsernameProblemLanguageResultExecution timeMemory
1256066minhpkBuilding 4 (JOI20_building4)C++20
11 / 100
2091 ms46640 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
int z[1000005];
int t[1000005];
pair<int,int> dp[1000005][2];
int inf=1e16;
pair<int,int> combine(pair<int,int> a,pair<int,int> b,int add){
     return  make_pair(min(a.first,b.first+add),max(a.second,b.second+add));
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    int n=2*a;
    for (int i=1;i<=n;i++){
         cin >> z[i];
    }
    for (int i=1;i<=n;i++){
         cin >> t[i];
    }
    for  (int i=1;i<=n;i++){
         for (int j=0;j<=1;j++){
              dp[i][j]={inf,-inf};
         }
    }
    dp[1][0]={1,1};
    dp[1][1]={0,0};
    for (int i=2;i<=n;i++){
         if (z[i]>=z[i-1]){
             dp[i][0]=combine(dp[i][0],dp[i-1][0],1);
         }
         if (z[i]>=t[i-1]){
             dp[i][0]=combine(dp[i][0],dp[i-1][1],1);
         }
         if (t[i]>=z[i-1]){
             dp[i][1]=combine(dp[i][1],dp[i-1][0],0);
         }
         if (t[i]>=t[i-1]){
             dp[i][1]=combine(dp[i][1],dp[i-1][1],0);
         }
    }
    int prv=inf;
    int cnt=a;
    string s="";
    for (int i=n;i>=1;i--){
         if (dp[i][0].first<=cnt && cnt<= dp[i][0].second && z[i]<=prv){
             s='A'+s;
             cnt--;
             prv=z[i];
         }else if (dp[i][1].first<=cnt && cnt<= dp[i][1].second && t[i]<=prv){
             s='B'+s;
             prv=t[i];
         }else{
             cout << -1 << "\n";
             return 0;
         }
    }
    cout << s << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...