oj.uz

Submission #944971

# Submission time Handle Problem Language Result Execution time Memory
944971 2024-03-13T09:12:38 Z vjudge1 Building 4 (JOI20_building4) C++17
0 / 100
 18 ms 10588 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#warning That's the baby, that's not my baby

typedef long long ll;

const int NMAX = 1E6;

int dpmin[NMAX + 2];
int dpmax[NMAX + 2];
int pmin[NMAX + 2];
int pmax[NMAX + 2];

int a[NMAX + 2], b[NMAX + 2];

int main() {
  #ifndef LOCAL
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
  #endif

  int n;
  std::cin >> n;
  n *= 2;

  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    std::cin >> b[i];
  }

  for (int i = 1; i <= n; i++) {
    dpmin[i] = 1e9;
  }

  for (int i = 1; i <= n; i++) {
    bool ok = true;
    dpmax[i] = -1e9;
    for (int j = i - 1; j >= 0 && ok; j--) {
      if (j != i - 1) {
        ok &= (a[j] <= a[j + 1]);
      }
      if (b[i] >= b[j]) {
        if (j != i - 1) {
          if (a[i - 1] > b[i]) {
            break;
          }
          if (b[j] > a[j + 1]) {
            continue;
          }
        }
        if (dpmin[j] + 1 <= dpmin[i]) {
          dpmin[i] = dpmin[j] + 1;
          pmin[i] = j;
        }
        if (dpmax[j] + 1 >= dpmax[i]) {
          dpmax[i] = dpmax[j] + 1;
          pmax[i] = j;
        }
      }
    }
  }

  int m = n / 2;

  bool incr = true;

//  for (int i = 1; i <= n; i++) {
//    std::cout << i << ": " << dpmin[i] << " <> " << dpmax[i] << '\n';
//  }
//
//  for (int i = 1; i <= n; i++) {
//    std::cout << i << ": " << pmin[i] << " <> " << pmax[i] << '\n';
//  }

  for (int i = n; i > 0 && incr; i--) {
    if (dpmin[i] <= m && m <= dpmax[i] && (i == n || b[i] <= a[i + 1])) {
      int p = i;
      int cntB = 0;
      std::string answer(n + 1, 'A');
      while (p > 0) {
        cntB++;
        answer[p] = 'B';
        p = pmin[p];
      }
      p = i;
      while (cntB < m) {
//        std::cout << "! " << p << ' ' << dpmax[i] << '\n';
        if (answer[p] == 'A') {
          cntB++;
          answer[p] = 'B';
        }
        p = pmax[p];
      }
      answer.erase(answer.begin());
      std::cout << answer;
      return 0;
    }
    if (i <= n - 2) {
      incr &= (a[i + 1] <= a[i + 2]);
    }
  }

  std::cout << -1;


  return 0;
}

Compilation message

building4.cpp:6:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    6 | #warning That's the baby, that's not my baby
      |  ^~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 17 ms 10588 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 18 ms 10588 KB Output is correct
17 Incorrect 2 ms 10588 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 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 17 ms 10588 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 18 ms 10588 KB Output is correct
17 Incorrect 2 ms 10588 KB Output isn't correct
18 Halted 0 ms 0 KB -