Submission #312914

#	Time	Username	Problem	Language	Result	Execution time	Memory
312914		quocnguyen1012	Building 4 (JOI20_building4)	C++14	0 / 100	1 ms	384 KiB

building4

#include <bits/stdc++.h>

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

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

template<class T>
bool chkmin(T & x, T val) {
  if (x > val) {
    x = val;
    return true;
  }
  return false;
}

const int maxn = 1e6 + 5;

int a[maxn][2], N;
pair<ll, int> f[maxn][2];
int trace[maxn][2];

pair<ll, int> calc(int cost) {
  for (int i = 1; i <= 2 * N; ++i) {
    f[i][0] = f[i][1] = mp(1e16, 1e9);
    for (int c = 0; c < 2; ++c) {
      for (int pr = 0; pr < 2; ++pr) {
        if (a[i][c] >= a[i - 1][pr]) {
          if (c == 0)
            f[i][c] = min(f[i][c], f[i - 1][pr]);
          else
            f[i][c] = min(f[i][c], mp(f[i - 1][pr].fi + cost, f[i - 1][pr].se + 1));
        }
      }
    }
  }
  return min(f[2 * N][0], f[2 * N][1]);
}

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;
  for (int i = 1; i <= 2 * N; ++i)
    cin >> a[i][0];
  for (int i = 1; i <= 2 * N; ++i)
    cin >> a[i][1];


  int l = -maxn, r = 0, mid;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (calc(mid).se > N) l = mid + 1;
    else r = mid - 1;
  }
  if (calc(l).se != N) {
    cout << -1;
    return 0;
  }

  for (int i = 1; i <= 2 * N; ++i) {
    f[i][0] = f[i][1] = mp(1e16, 1e9);
    for (int c = 0; c < 2; ++c) {
      for (int pr = 0; pr < 2; ++pr) {
        if (a[i][c] >= a[i - 1][pr]) {
          if (c == 0) {
            if (chkmin(f[i][c], f[i - 1][pr])) {
              trace[i][c] = pr;
            }
          } else {
            if (chkmin(f[i][c], mp(f[i - 1][pr].fi + l, f[i - 1][pr].se + 1))) {
              trace[i][c] = pr;
            }
          }
        }
      }
    }
  }
  string str;
  int now = (f[N * 2][0] > f[N * 2][1] ? 1 : 0);
  for (int i = 2 * N; i >= 1; --i) {
    if (now) str += 'B';
    else str += 'A';
    now = trace[i][now];
  }
  reverse(str.begin(), str.end());
  cout << str;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:60:25: warning: unused variable 'mid' [-Wunused-variable]
   60 |   int l = -maxn, r = 0, mid;
      |                         ^~~

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