oj.uz

Submission #1002428

# Submission time Handle Problem Language Result Execution time Memory
1002428 2024-06-19T14:48:08 Z MilosMilutinovic Swap (BOI16_swap) C++14
68 / 100
 656 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    --a[i];
  }
  vector<vector<vector<int>>> dp(n);
  vector<map<int, int>> idx(n);
  auto Merge = [&](int x, vector<int> va, vector<int> vb) {
    vector<int> v(1, x);
    int pa = 0, pb = 0;
    for (int pw = 1; pa < (int) va.size(); pw *= 2) {
      for (int iter = 0; iter < pw; iter++) {
        if (pa < (int) va.size()) {
          v.push_back(va[pa]);
          pa += 1;
        } else {
          break;
        }
      }
      for (int iter = 0; iter < pw; iter++) {
        if (pb < (int) vb.size()) {
          v.push_back(vb[pb]);
          pb += 1;
        } else {
          break;
        }
      }
    }
    return v;
  };
  function<vector<int>(int, int)> Solve = [&](int i, int v) {
    if (i >= n) {
      return vector<int>{};
    }
    if (!idx[i][v]) {
      idx[i][v] = (int) dp[i].size();
      dp[i].push_back({});
    }
    int p = idx[i][v];
    if (!dp[i][p].empty()) {
      return dp[i][p];
    }
    int L = i * 2 + 1, R = i * 2 + 2;
    if (L >= n) {
      return dp[i][p] = {v};
    }
    if (R >= n) {
      if (v < a[L]) {
        dp[i][p] = Merge(v, Solve(L, a[L]), {});
      } else {
        dp[i][p] = Merge(a[L], Solve(L, v), {});
      }
      return dp[i][p];
    }
    if (v <= a[L] && v <= a[R]) {
      dp[i][p] = Merge(v, Solve(L, a[L]), Solve(R, a[R]));
    } else if (a[L] <= v && a[L] <= a[R]) {
      dp[i][p] = Merge(a[L], Solve(L, v), Solve(R, a[R]));
    } else {
      dp[i][p] = min(Merge(a[R], Solve(L, a[L]), Solve(R, v)), Merge(a[R], Solve(L, v), Solve(R, a[L])));
    }
    return dp[i][p];
  };
  vector<int> res = Solve(0, a[0]);
  for (int i = 0; i < (int) res.size(); i++) {
    cout << res[i] + 1 << " ";
  }
  cout << '\n';
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 3 ms 1448 KB Output is correct
15 Correct 4 ms 1476 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 3 ms 1448 KB Output is correct
15 Correct 4 ms 1476 KB Output is correct
16 Correct 69 ms 27372 KB Output is correct
17 Correct 72 ms 27096 KB Output is correct
18 Correct 79 ms 27736 KB Output is correct
19 Correct 486 ms 107588 KB Output is correct
20 Correct 489 ms 106428 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 3 ms 1448 KB Output is correct
15 Correct 4 ms 1476 KB Output is correct
16 Correct 69 ms 27372 KB Output is correct
17 Correct 72 ms 27096 KB Output is correct
18 Correct 79 ms 27736 KB Output is correct
19 Correct 486 ms 107588 KB Output is correct
20 Correct 489 ms 106428 KB Output is correct
21 Correct 371 ms 116404 KB Output is correct
22 Correct 377 ms 116448 KB Output is correct
23 Correct 370 ms 116104 KB Output is correct
24 Runtime error 656 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -