Submission #954746

#	Time	Username	Problem	Language	Result	Execution time	Memory
954746		abczz	Building 4 (JOI20_building4)	C++14	0 / 100	5 ms	7004 KiB

building4

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#define ll long long
#define ld long double

using namespace std;

bool visited[1000000][2], X[1000000][2], B[1000000];
string S;
vector <array<ll, 2>> V, R;
ll n, s, k, p, x, mn, mx, A[1000000][2], cnt[1000000];
void dfs(ll u, ll x) {
  visited[u][x] = 1;
  if (u == n-1) {
    X[u][x] = 1;
    return;
  }
  if (A[u][x] <= A[u+1][0]) {
    if (!visited[u+1][0]) dfs(u+1, 0);
    X[u][x] |= X[u+1][0];
  }
  if (A[u][x] <= A[u+1][1]) {
    if (!visited[u+1][1]) dfs(u+1, 1);
    X[u][x] |= X[u+1][1];
  }
}
int main() {
  cin >> n;
  n *= 2;
  for (int j=0; j<2; ++j) {
    for (int i=0; i<n; ++i) cin >> A[i][j];
  }
  dfs(0, 0);
  dfs(0, 1);
  if (!X[0][0] && !X[0][1]) {
    cout << "-1\n";
    return 0;
  }
  for (int i=0; i<n; ++i) {
    S += '.';
    cnt[i] = X[i][0] + X[i][1];
    if (cnt[i] == 1) {
      if (X[i][0]) {
        S.back() = 'A';
        ++s;
      }
      else {
        S.back() = 'B';
        --s;
      }
    }
  }
  k = 0, p = 1e18;
  for (ll i=0; i+1<n; ++i) {
    if (cnt[i] == 1 || cnt[i+1] == 1 || max(A[i][0], A[i][1]) <= min(A[i+1][0], A[i+1][1])) {
      if (p != 1e18) {
        if (A[i][0] > A[i][1]) ++k;
        else --k;
        mn = mx = k;
        for (int j=p; j<=i; ++j) {
          B[j] = 1;
          if (A[j][0] > A[j][1]) k -= 2;
          else k += 2;
          mn = min(mn, k);
          mx = max(mx, k);
        }
        R.push_back({p, i});
        V.push_back({mn, mx});
        k = 0, p = 1e18;
      }
      continue;
    }
    p = min(p, i);
    if (A[i][0] > A[i][1]) ++k;
    else --k;
  }
  if (p != 1e18) {
    if (A[n-1][0] > A[n-1][1]) ++k;
    else --k;
    mn = mx = k;
    for (int j=p; j<n; ++j) {
      B[j] = 1;
      if (A[j][0] > A[j][1]) k -= 2;
      else k += 2;
      mn = min(mn, k);
      mx = max(mx, k);
    }
    R.push_back({p, n-1});
    V.push_back({mn, mx});
    k = 0, p = 1e18;
  }
  k = 0;
  for (int i=0; i<n; ++i) {
    if (cnt[i] == 2 && !B[i]) ++k;
  }
  for (auto [l, r] : V) {
    s += l;
  }
  for (auto &[l, r] : V) {
    while (s < 0 && l < r) {
      s += 2;
      l += 2;
    }
  }
  if (s + k < 0 || s - k > 0) {
    cout << "-1\n";
    return 0;
  }
  int i = 0;
  for (auto [l, r] : R) {
    x = 0;
    for (int i=l; i<=r; ++i) {
      if (A[i][0] > A[i][1]) {
        S[i] = 'A';
        ++x;
      }
      else {
        S[i] = 'B';
        --x;
      }
    }
    if (x == V[i][0]) continue;
    for (int i=l; i<=r; ++i) {
      if (A[i][0] > A[i][1]) {
        S[i] = 'B';
        x -= 2;
      }
      else {
        S[i] = 'A';
        x += 2;
      }
      if (x == V[i][0]) break;
    }
    ++i;
  }
  for (int i=0; i<n; ++i) {
    if (cnt[i] == 2 && !B[i]) {
      if (s <= 0) {
        ++s;
        S[i] = 'A';
      }
      else {
        --s;
        S[i] = 'B';
      }
    }
  }
  cout << S << '\n';
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:99:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |   for (auto [l, r] : V) {
      |             ^
building4.cpp:102:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |   for (auto &[l, r] : V) {
      |              ^
building4.cpp:113:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |   for (auto [l, r] : R) {
      |             ^

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