Submission #868792

#	Time	Username	Problem	Language	Result	Execution time	Memory
868792		awu	Building 4 (JOI20_building4)	C++14	100 / 100	205 ms	68884 KiB

building4

#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define ll long long
// #define double long double
#define all(x) x.begin(), x.end()
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
#define f first
#define s second
using pii = pair<int, int>;
// #define endl '\n'

const ll inf = 1ll << 60;

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n; cin >> n; n *= 2;
  vector<int> a(n), b(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for(int i = 0; i < n; i++) {
    cin >> b[i];
  }
  vector<pair<pii, pii>> dp(n, {{-1, -1}, {-1, -1}});
  dp[n - 1] = {{1, 1}, {0, 0}};
  auto merge = [&](pii a, pii b) {
    if(min(a, b) == pii{-1, -1}) return max(a, b);
    return pii{min(a.f, b.f), max(a.s, b.s)};
  };
  for(int i = n - 2; i >= 0; i--) {
    if(a[i] <= a[i + 1]) {
      dp[i].f = merge(dp[i].f, dp[i + 1].f);
    }
    if(a[i] <= b[i + 1]) {
      dp[i].f = merge(dp[i].f, dp[i + 1].s);
    }
    if(dp[i].f != pii{-1, -1}) {
      dp[i].f.f++;
      dp[i].f.s++;
    }
    if(b[i] <= a[i + 1]) {
      dp[i].s = merge(dp[i].s, dp[i + 1].f);
    }
    if(b[i] <= b[i + 1]) {
      dp[i].s = merge(dp[i].s, dp[i + 1].s);
    }
    // cout << i << " " << dp[i].f.f << " " << dp[i].f.s << " " << dp[i].s.f << " " << dp[i].s.s << endl;
  }
  int rem = n / 2;
  int last = -1;
  string ans;
  auto die = [&]() {
    cout << -1 << endl;
    exit(0);
  };
  for(int i = 0; i < n; i++) {
    if(last <= a[i] && dp[i].f.f <= rem && rem <= dp[i].f.s) {
      ans += "A";
      last = a[i];
      rem--;
    } else if(last <= b[i] && dp[i].s != pii{-1, -1}) {
      ans += "B";
      last = b[i];
    } else {
      die();
    }
  }
  if(count(all(ans), 'A') != n / 2) die();
  cout << ans << endl;
}

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