oj.uz

Submission #954746

# Submission time Handle Problem Language Result Execution time Memory
954746 2024-03-28T13:31:34 Z abczz Building 4 (JOI20_building4) C++14
0 / 100
 5 ms 7004 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 6844 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 4 ms 6748 KB Output is correct
13 Correct 5 ms 6748 KB Output is correct
14 Correct 4 ms 6748 KB Output is correct
15 Correct 3 ms 7004 KB Output is correct
16 Correct 3 ms 7000 KB Output is correct
17 Incorrect 4 ms 7004 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 6844 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 4 ms 6748 KB Output is correct
13 Correct 5 ms 6748 KB Output is correct
14 Correct 4 ms 6748 KB Output is correct
15 Correct 3 ms 7004 KB Output is correct
16 Correct 3 ms 7000 KB Output is correct
17 Incorrect 4 ms 7004 KB Output isn't correct
18 Halted 0 ms 0 KB -