Submission #222562

#	Time	Username	Problem	Language	Result	Execution time	Memory
222562		quocnguyen1012	Building 4 (JOI20_building4)	C++14	100 / 100	407 ms	132488 KiB

building4

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e6 + 5, inf = 1e9;

int N;
ll a[maxn][2];
ii f[maxn][2];
bool vis[maxn][2];

void trav(int pos, int t)
{
  if(vis[pos][t]) return;
  vis[pos][t] = true;
  int mn = inf, mx = -inf;
  if(a[pos][t] <= a[pos + 1][1]){
    trav(pos + 1, 1);
    mn = min(mn, f[pos + 1][1].fi);
    mx = max(mx, f[pos + 1][1].se);
  }
  if(a[pos][t] <= a[pos + 1][0]){
    trav(pos + 1, 0);
    mn = min(mn, f[pos + 1][0].fi + 1);
    mx = max(mx, f[pos + 1][0].se + 1);
  }
  //cerr << pos << ' ' << t << ' ' << mn << ' ' << mx << '\n';
  f[pos][t] = mp(mn, mx);
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N; N *= 2;
  for(int j = 0; j < 2; ++j){
    for(int i = 1; i <= N; ++i)
      cin >> a[i][j];
  }
  vis[N][0] = vis[N][1] = true;
  trav(0, 0);
  if(f[0][0].fi > N / 2  || f[0][0].fi > f[0][0].se){
    cout << -1;
    return 0;
  }
  int last = 0;
  int cur = N / 2;
  for(int i = 1; i <= N; ++i){
    if(a[i][0] >= a[i - 1][last] && f[i][0].fi <= cur - 1 && cur - 1 <= f[i][0].se){
      last = 0;
      --cur;
      cout << 'A';
    }
    else{
      last = 1;
      cout << 'B';
    }
  }
}

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