oj.uz

Submission #258292

# Submission time Handle Problem Language Result Execution time Memory
258292 2020-08-05T16:18:28 Z rama_pang Swap (BOI16_swap) C++14
0 / 100
 26 ms 37888 KB 
#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> a(3);
  a[0] = x, a[1] = A[n * 2], a[2] = A[n * 2 + 1];
  if (a[0] < min(a[1], a[2])) {
    track[n][x] = 0;
    return dp[n][x] = n;
  } 
  if (a[1] < min(a[0], a[2])) {
    dp[n][x] = Dp(n * 2, x);
    track[n][x] = 1;
    return dp[n][x];
  }
  if (a[2] < min(a[0], a[1])) {
    int res = 1e9;
    int nxt = 0;
    for (int l = 0; l < 2; l++) {
      if (l) swap(a[0], a[1]);
      swap(a[0], 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 + 2;
        }
      } else {
        if (Dp(n * 2 + 1, a[2]) < res) {
          res = Dp(n * 2 + 1, a[2]);
          nxt = l + 2;
        }
      }
      swap(a[0], a[2]);
      if (l) swap(a[0], a[1]);
    }
    track[n][x] = nxt;
    return dp[n][x] = res;
  }
  return -1;
}

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.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37888 KB Output is correct
2 Correct 25 ms 37888 KB Output is correct
3 Correct 26 ms 37888 KB Output is correct
4 Incorrect 21 ms 37888 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37888 KB Output is correct
2 Correct 25 ms 37888 KB Output is correct
3 Correct 26 ms 37888 KB Output is correct
4 Incorrect 21 ms 37888 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37888 KB Output is correct
2 Correct 25 ms 37888 KB Output is correct
3 Correct 26 ms 37888 KB Output is correct
4 Incorrect 21 ms 37888 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37888 KB Output is correct
2 Correct 25 ms 37888 KB Output is correct
3 Correct 26 ms 37888 KB Output is correct
4 Incorrect 21 ms 37888 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37888 KB Output is correct
2 Correct 25 ms 37888 KB Output is correct
3 Correct 26 ms 37888 KB Output is correct
4 Incorrect 21 ms 37888 KB Output isn't correct
5 Halted 0 ms 0 KB -