Submission #258290

#	Time	Username	Problem	Language	Result	Execution time	Memory
258290		rama_pang	Swap (BOI16_swap)	C++14	0 / 100	29 ms	37880 KiB

swap

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

const int MAXN = 400005;
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

int Dp(int n, int x) {
  if (n > N) return INF;
  if (dp[n].count(x)) return dp[n][x];
  vector<int> elems;
  if (x < min(A[n * 2], A[n * 2 + 1])) {
    track[n][x] = 0;
    return dp[n][x] = n;
  }
  vector<int> a(3);
  a[0] = x, a[1] = A[n * 2], a[2] = A[n * 2 + 1];

  int res = 1e9;
  int nxt = 0;
  for (int l = 0; l < 2; l++) {
    for (int r = 0; r < 2; r++) {
      if (l) swap(a[0], a[1]);
      if (r) swap(a[0], a[2]);
      if (a[0] < min(a[1], a[2])) {
        if (a[1] == min(a[1], a[2])) {
          if (Dp(n * 2 + 0, a[1]) < res) {
            res = Dp(n * 2 + 0, a[1]);
            nxt = l + r * 2;
          }
        } else {
          if (Dp(n * 2 + 1, a[2]) < res) {
            res = Dp(n * 2 + 1, a[2]);
            nxt = l + r * 2;
          }
        }
      }
      if (r) swap(a[0], a[2]);
      if (l) swap(a[0], a[1]);
    }
  }
  track[n][x] = nxt;
  return dp[n][x] = res;
}

void Trace(int n, int x) {
  if (n > N) return;
  Dp(n, x);
  assert(A[n] == x);
  if (track[n][x] & 1) swap(A[n], A[n * 2 + 0]);
  if (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];
    A[i + N] = INF;
  }
  Trace(1, A[1]);
  for (int i = 1; i <= N; i++) {
    if (i > 1) {
      cout << " ";
    }
    cout << A[i];
  }
  cout << "\n";
  return 0;
}

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