oj.uz

Submission #1002424

# Submission time Handle Problem Language Result Execution time Memory
1002424 2024-06-19T14:45:40 Z MilosMilutinovic Swap (BOI16_swap) C++14
48 / 100
 1000 ms 156748 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) {
      return dp[i][p] = min(Merge(v, Solve(L, a[L]), {}), 
                            Merge(a[L], Solve(L, v), {}));
    }
    return dp[i][p] = min({Merge(v, Solve(L, a[L]), Solve(R, a[R])), 
                           Merge(a[L], Solve(L, v), Solve(R, a[R])),
                           Merge(a[R], Solve(L, a[L]), Solve(R, v)),
                           Merge(a[R], Solve(L, v), Solve(R, a[L]))});
  };
  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 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 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 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 376 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 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 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 376 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 9 ms 2208 KB Output is correct
12 Correct 8 ms 2248 KB Output is correct
13 Correct 11 ms 2260 KB Output is correct
14 Correct 7 ms 2136 KB Output is correct
15 Correct 7 ms 2260 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 376 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 9 ms 2208 KB Output is correct
12 Correct 8 ms 2248 KB Output is correct
13 Correct 11 ms 2260 KB Output is correct
14 Correct 7 ms 2136 KB Output is correct
15 Correct 7 ms 2260 KB Output is correct
16 Correct 989 ms 156524 KB Output is correct
17 Execution timed out 1059 ms 156748 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 376 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 9 ms 2208 KB Output is correct
12 Correct 8 ms 2248 KB Output is correct
13 Correct 11 ms 2260 KB Output is correct
14 Correct 7 ms 2136 KB Output is correct
15 Correct 7 ms 2260 KB Output is correct
16 Correct 989 ms 156524 KB Output is correct
17 Execution timed out 1059 ms 156748 KB Time limit exceeded
18 Halted 0 ms 0 KB -