제출 #258309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258309		rama_pang	Swap (BOI16_swap)	C++14	100 / 100	833 ms	165880 KiB

swap

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 200005;
const int INF = 1e9;
 
int N;
int A[MAXN];
 
map<int, int> dp[MAXN]; 
// dp[n][x] = minimum sequence in subtree of n if the root's value is x
// we only keep track of where min(cur, lc, rc)'s value end up in the dp
 
int Dp(int n, int x, int trace) {
  if (n > N) return INF;
  if (!trace && dp[n].count(x)) return dp[n][x];
  if (trace) Dp(n, x, 0);
  auto Trace = [&](int tid) {
    if (!trace) return;
    if (n * 2 + 0 <= N && tid & 1) swap(A[n], A[n * 2 + 0]);
    if (n * 2 + 1 <= N && tid & 2) swap(A[n], A[n * 2 + 1]);
    if (n * 2 + 0 <= N) Dp(n * 2 + 0, A[n * 2 + 0], 1);
    if (n * 2 + 1 <= N) Dp(n * 2 + 1, A[n * 2 + 1], 1);
  };
  vector<int> a(3);
  a[0] = x;
  a[1] = (n * 2 + 0 <= N ? A[n * 2 + 0] : INF);
  a[2] = (n * 2 + 1 <= N ? A[n * 2 + 1] : INF);
  if (a[0] < min(a[1], a[2])) {
    Trace(0);
    return dp[n][x] = n;
  } 
  if (a[1] < min(a[0], a[2])) {
    Trace(1);
    return dp[n][x] = Dp(n * 2, a[0], 0);
  }
  if (a[2] < min(a[0], a[1])) {
    int xl = Dp(n * 2 + 0, a[0], 0);
    int xr = Dp(n * 2 + 1, a[0], 0);
    int yl = Dp(n * 2 + 0, a[1], 0);
    int yr = Dp(n * 2 + 1, a[1], 0);
    if (min(xl, yr) < min(xr, yl)) {
      Trace(3);
      return dp[n][x] = xl;
    }
    if (min(xl, yr) > min(xr, yl)) {
      Trace(2);
      return dp[n][x] = xr;
    }
    if (a[0] < a[1]) {
      if (xl < xr) {
        Trace(3);
        return dp[n][x] = xl;
      } else {
        Trace(2);
        return dp[n][x] = xr;
      }
    } else {
      if (yr < yl) {
        Trace(3);
        return dp[n][x] = xl;
      } else {
        Trace(2);
        return dp[n][x] = xr;
      }
    }
  }
  return -1;
}
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
 
  cin >> N;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
  }
  Dp(1, A[1], 1);
  for (int i = 1; i <= N; i++) {
    if (i > 1) {
      cout << " ";
    }
    cout << A[i];
  }
  cout << "\n";
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32