Submission #1198050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198050		mychecksedad	Building 4 (JOI20_building4)	C++20	100 / 100	253 ms	135556 KiB

building4

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int n;
array<int, 2> a[N], dp[N][2];
vector<int> g[N][2];
void solve(){
  cin >> n;
  n *= 2;
  for(int i = 1; i <= n; ++i){
    cin >> a[i][0];
  }
  for(int i = 1; i <= n; ++i){
    cin >> a[i][1];
  }
  for(int i = 1; i < n; ++i){
    if(a[i + 1][0] >= a[i][0]) g[i][0].pb(0);
    if(a[i + 1][1] >= a[i][0]) g[i][0].pb(1);
    if(a[i + 1][0] >= a[i][1]) g[i][1].pb(0);
    if(a[i + 1][1] >= a[i][1]) g[i][1].pb(1);
  }
  dp[n][0] = {1, 1};
  dp[n][1] = {0, 0};
  for(int i = n - 1; i >= 1; --i){
    for(int r = 0; r < 2; ++r){
      dp[i][r] = {MOD, 0};
      for(int u: g[i][r]){
        dp[i][r][0] = min(dp[i][r][0], dp[i + 1][u][0] + (r == 0));
        dp[i][r][1] = max(dp[i][r][1], dp[i + 1][u][1] + (r == 0));
      }
    }
  }
  int st, num = n/2; // current index, state, number of A's
  string res;
  if(dp[1][0][0] <= n/2 && n/2 <= dp[1][0][1]){
    st = 0;
    num--;
    res += 'A';
  }else if(dp[1][1][0] <= n/2 && n/2 <= dp[1][1][1]){
    st = 1;
    res += 'B'; 
  }else{
    cout << -1;
    return;
  }
  for(int i = 2; i <= n; ++i){
    for(int u: g[i - 1][st]){
      if(dp[i][u][0] <= num && num <= dp[i][u][1]){
        st = u;
        if(u == 0){
          res += 'A';
          --num;
        }else{
          res += 'B';
        }
        break;
      }
    }
  }
  cout << res;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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