oj.uz

Submission #258309

# Submission time Handle Problem Language Result Execution time Memory
258309 2020-08-05T17:15:22 Z rama_pang Swap (BOI16_swap) C++14
100 / 100
 833 ms 165880 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 8 ms 9728 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 5 ms 9728 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 8 ms 9728 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 5 ms 9728 KB Output is correct
6 Correct 6 ms 9728 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 5 ms 9728 KB Output is correct
9 Correct 6 ms 9856 KB Output is correct
10 Correct 6 ms 9728 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 8 ms 9728 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 5 ms 9728 KB Output is correct
6 Correct 6 ms 9728 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 5 ms 9728 KB Output is correct
9 Correct 6 ms 9856 KB Output is correct
10 Correct 6 ms 9728 KB Output is correct
11 Correct 6 ms 9856 KB Output is correct
12 Correct 6 ms 9856 KB Output is correct
13 Correct 7 ms 9856 KB Output is correct
14 Correct 8 ms 10112 KB Output is correct
15 Correct 7 ms 10112 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 8 ms 9728 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 5 ms 9728 KB Output is correct
6 Correct 6 ms 9728 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 5 ms 9728 KB Output is correct
9 Correct 6 ms 9856 KB Output is correct
10 Correct 6 ms 9728 KB Output is correct
11 Correct 6 ms 9856 KB Output is correct
12 Correct 6 ms 9856 KB Output is correct
13 Correct 7 ms 9856 KB Output is correct
14 Correct 8 ms 10112 KB Output is correct
15 Correct 7 ms 10112 KB Output is correct
16 Correct 39 ms 15992 KB Output is correct
17 Correct 38 ms 15992 KB Output is correct
18 Correct 40 ms 16120 KB Output is correct
19 Correct 188 ms 43992 KB Output is correct
20 Correct 213 ms 43748 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 8 ms 9728 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 5 ms 9728 KB Output is correct
6 Correct 6 ms 9728 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 5 ms 9728 KB Output is correct
9 Correct 6 ms 9856 KB Output is correct
10 Correct 6 ms 9728 KB Output is correct
11 Correct 6 ms 9856 KB Output is correct
12 Correct 6 ms 9856 KB Output is correct
13 Correct 7 ms 9856 KB Output is correct
14 Correct 8 ms 10112 KB Output is correct
15 Correct 7 ms 10112 KB Output is correct
16 Correct 39 ms 15992 KB Output is correct
17 Correct 38 ms 15992 KB Output is correct
18 Correct 40 ms 16120 KB Output is correct
19 Correct 188 ms 43992 KB Output is correct
20 Correct 213 ms 43748 KB Output is correct
21 Correct 154 ms 34884 KB Output is correct
22 Correct 145 ms 34808 KB Output is correct
23 Correct 162 ms 34936 KB Output is correct
24 Correct 833 ms 165700 KB Output is correct
25 Correct 814 ms 165880 KB Output is correct