Submission #1135832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135832		huutuan	Building 4 (JOI20_building4)	C++20	100 / 100	127 ms	26036 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+10;
int a[N], b[N], n;
pair<int, int> f[N][2];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n*2; ++i) cin >> a[i];
   for (int i=1; i<=n*2; ++i) cin >> b[i];
   f[1][0]={1, 1};
   f[1][1]={0, 0};
   for (int i=2; i<=n*2; ++i){
      f[i][0]={-1, -1};
      f[i][1]={-1, -1};
      if (a[i-1]<=a[i] && f[i-1][0].first!=-1){
         f[i][0]={f[i-1][0].first+1, f[i-1][0].second+1};
      }
      if (b[i-1]<=a[i] && f[i-1][1].first!=-1){
         if (f[i][0].first==-1) f[i][0]={f[i-1][1].first+1, f[i-1][1].second+1};
         else{
            assert(max(f[i-1][0].first, f[i-1][1].first)<=min(f[i-1][0].second, f[i-1][1].second)+1);
            f[i][0]={min(f[i][0].first, f[i-1][1].first+1), max(f[i][0].second, f[i-1][1].second+1)};
         }
      }
      if (b[i-1]<=b[i] && f[i-1][1].first!=-1){
         f[i][1]={f[i-1][1].first, f[i-1][1].second};
      }
      if (a[i-1]<=b[i] && f[i-1][0].first!=-1){
         if (f[i][1].first==-1) f[i][1]={f[i-1][0].first, f[i-1][0].second};
         else{
            assert(max(f[i-1][0].first, f[i-1][1].first)<=min(f[i-1][0].second, f[i-1][1].second)+1);
            f[i][1]={min(f[i][1].first, f[i-1][0].first), max(f[i][1].second, f[i-1][0].second)};
         }
      }
   }
   string ans;
   auto trace=[&](auto &&self, int i, int j, int sum) -> void {
      if (j==0){
         --sum;
         ans.push_back('A');
         if (i==1) return;
         if (a[i-1]<=a[i] && f[i-1][0].first<=sum && sum<=f[i-1][0].second && sum){
            self(self, i-1, 0, sum);
         }else{
            self(self, i-1, 1, sum);
         }
      }else{
         ans.push_back('B');
         if (i==1) return;
         if (b[i-1]<=b[i] && f[i-1][1].first<=sum && sum<=f[i-1][1].second){
            self(self, i-1, 1, sum);
         }else{
            self(self, i-1, 0, sum);
         }
      }
   };
   if (f[n*2][0].first<=n && n<=f[n*2][0].second){
      trace(trace, n*2, 0, n);
      reverse(ans.begin(), ans.end());
      cout << ans << '\n';
   }else if (f[n*2][1].first<=n && n<=f[n*2][1].second){
      trace(trace, n*2, 1, n);
      reverse(ans.begin(), ans.end());
      cout << ans << '\n';
   }else{
      cout << -1 << '\n';
   }
   return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 89 / 89