Submission #217160

#	Time	Username	Problem	Language	Result	Execution time	Memory
217160		rama_pang	Building 4 (JOI20_building4)	C++14	100 / 100	629 ms	191468 KiB

building4

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

const int MAXN = 500005;

int N;
int A[MAXN * 2];
int B[MAXN * 2];


namespace solution_naive {

int memo[5005][5005][2];
string ans;

void read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  
  cin >> N;
  for (int i = 1; i <= 2 * N; i++) {
    cin >> A[i];
  }
  for (int i = 1; i <= 2 * N; i++) {
    cin >> B[i];
  }
  A[0] = B[0] = 0;
  A[2 * N + 1] = B[2 * N + 1] = 2e9;
}

int dp(int cur, int a, int last) {
  if (a > N) return 0;
  if (cur == 2 * N + 1) return a == N;
  if (memo[cur][a][last] != -1) return memo[cur][a][last];
  int res = 0;
  int prv = (last == 0 ? A[cur - 1] : B[cur - 1]);

  if (prv <= A[cur]) res = max(res, dp(cur + 1, a + 1, 0));
  if (prv <= B[cur]) res = max(res, dp(cur + 1, a, 1));
  
  return memo[cur][a][last] = res;
}

void trace(int cur, int a, int last) {
  if (cur == 2 * N + 1) return;
  int res = 0;
  int prv = (last == 0 ? A[cur - 1] : B[cur - 1]);
  if (prv <= A[cur] && dp(cur + 1, a + 1, 0) == 1) {
    ans.push_back('A');
    trace(cur + 1, a + 1, 0);
  } else if (prv <= B[cur] && dp(cur + 1, a, 1) == 1) {
    ans.push_back('B');
    trace(cur + 1, a, 1);
  }
}

void solve() {
  read();
  memset(memo, -1, sizeof(memo));
  trace(1, 0, 0);
  if (ans.empty()) ans = "-1";
  cout << ans << "\n";
}

} // NAMESPACE

namespace full_solution {

void read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  
  cin >> N;
  for (int i = 0; i < 2 * N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < 2 * N; i++) {
    cin >> B[i];
  }
}

vector<pair<int, int>> adj[MAXN * 4]; // (to, value)

void init() {
  for (int i = 0; i + 1 < 2 * N; i++) {
    if (A[i] <= A[i + 1]) adj[i * 2].emplace_back(i * 2 + 2, 1);
    if (A[i] <= B[i + 1]) adj[i * 2].emplace_back(i * 2 + 3, 0);
    if (B[i] <= A[i + 1]) adj[i * 2 + 1].emplace_back(i * 2 + 2, 1);
    if (B[i] <= B[i + 1]) adj[i * 2 + 1].emplace_back(i * 2 + 3, 0);
  }
  adj[4 * N].emplace_back(0, 1);
  adj[4 * N].emplace_back(1, 0);
}

int vis[MAXN * 4];
// set<int> all[MAXN * 4]; (all possible value of all possible paths)
pair<int, int> dp[MAXN * 4]; // all[n] has consecutive elements, save this interval in a dp of (min, max)

void dfs(int n) {
  if (vis[n]) return;
  vis[n] = 1;
  int mn = -1, mx = -1;

  // all[n] has consecutive elements due to nature of naive_dp's transition (shifting elements only by 1 position, then ORing them).

  for (auto &i : adj[n]) {
    dfs(i.first);
    if (dp[i.first] == make_pair(-1, -1)) {
      continue;
    }
    if (mn == -1 || mn > dp[i.first].first + i.second) {
      mn = dp[i.first].first + i.second;
    }
    if (mx == -1 || mx < dp[i.first].second + i.second) {
      mx = dp[i.first].second + i.second;
    }
  }
  dp[n] = make_pair(mn, mx);
}

string ans;

void trace(int n, int cur = N) {
  if (dp[n] == make_pair(-1, -1) || !(dp[n].first <= cur && cur <= dp[n].second)) {
    ans = "-1";
    return;
  }
  for (auto &i : adj[n]) {
    if (dp[i.first] != make_pair(-1, -1) && dp[i.first].first <= cur - i.second && cur - i.second <= dp[i.first].second) {
      if (i.second == 1) ans.push_back('A');
      if (i.second == 0) ans.push_back('B');
      
      trace(i.first, cur - i.second);
      return;
    }
  }
}

void solve() {
  read();
  init();

  dp[4 * N - 2] = make_pair(0, 0);
  dp[4 * N - 1] = make_pair(0, 0);
  vis[4 * N - 2] = 1;
  vis[4 * N - 1] = 1;

  dfs(4 * N);
  trace(4 * N);
  cout << ans << "\n";

}

} /// NAMESPACE

int main() {
  full_solution::solve();
  return 0;
}

Compilation message (stderr)

building4.cpp: In function 'void solution_naive::trace(int, int, int)':
building4.cpp:46:7: warning: unused variable 'res' [-Wunused-variable]
   int res = 0;
       ^~~

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