Submission #258300

#	Time	Username	Problem	Language	Result	Execution time	Memory
258300		rama_pang	Swap (BOI16_swap)	C++14	68 / 100	346 ms	141048 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
map<int, int> track[MAXN]; // we only keep track of where min(cur, lc, rc)'s value end up in the dp

int Dp(int n, int x) {
  if (n > N) return INF;
  if (dp[n].count(x)) return dp[n][x];
  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])) {
    Dp(n * 2 + 0, a[0]);
    Dp(n * 2 + 1, a[1]);
    track[n][x] = 0;
    return dp[n][x] = n;
  } 
  if (a[1] < min(a[0], a[2])) {
    Dp(n * 2 + 1, a[2]);
    track[n][x] = 1;
    return dp[n][x] = Dp(n * 2, x);
  }
  if (a[2] < min(a[0], a[1])) {
    int xl = Dp(n * 2 + 0, a[0]);
    int xr = Dp(n * 2 + 1, a[0]);
    int yl = Dp(n * 2 + 0, a[1]);
    int yr = Dp(n * 2 + 1, a[1]);
    if (min(xl, yr) < min(xr, yl)) {
      track[n][x] = 3;
      return dp[n][x] = xl;
    }
    if (min(xl, yr) > min(xr, yl)) {
      track[n][x] = 2;
      return dp[n][x] = xr;
    }
    if (a[0] < a[1]) {
      if (xl < xr) {
        track[n][x] = 3;
        return dp[n][x] = xl;
      } else {
        track[n][x] = 2;
        return dp[n][x] = xr;
      }
    } else if (a[1] < a[0]) {
      if (yr < yl) {
        track[n][x] = 3;
        return dp[n][x] = xl;
      } else {
        track[n][x] = 2;
        return dp[n][x] = xr;
      }
    }
  }
  return -1;
}

void Trace(int n, int x) {
  if (n > N) return;
  Dp(n, x);
  if (n * 2 + 0 <= N && track[n][x] & 1) swap(A[n], A[n * 2 + 0]);
  if (n * 2 + 1 <= N && track[n][x] & 2) swap(A[n], A[n * 2 + 1]);
  Trace(n * 2 + 0, A[n * 2 + 0]);
  Trace(n * 2 + 1, A[n * 2 + 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];
  }
  Trace(1, A[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: 0 / 32