oj.uz

Submission #1002480

# Submission time Handle Problem Language Result Execution time Memory
1002480 2024-06-19T15:11:34 Z MilosMilutinovic Swap (BOI16_swap) C++14
68 / 100
 964 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<int>> vals(n);
  vector<unordered_map<int, bool>> seen(n);
  function<void(int, int)> Build = [&](int i, int v) {
    if (i >= n || seen[i][v]) {
      return;
    }
    seen[i][v] = true;
    vals[i].push_back(v);
    int L = i * 2 + 1, R = i * 2 + 2;
    if (L >= n) {
      return;
    }
    if (R >= n) {
      if (v < a[L]) {
        Build(L, a[L]);
      } else {
        Build(L, v);
      }
      return;
    }
    if (v <= a[L] && v <= a[R]) {
      Build(L, a[L]);
      Build(R, a[R]);
    } else if (a[L] <= v && a[L] <= a[R]) {
      Build(L, v);
      Build(R, a[R]);
    } else {
      Build(L, a[L]);
      Build(R, v);
      Build(L, v);
      Build(R, a[L]);
    }
  };
  Build(0, a[0]);
  for (int i = 0; i < n; i++) {
    sort(vals[i].begin(), vals[i].end());
    vals[i].erase(unique(vals[i].begin(), vals[i].end()), vals[i].end());
  }
  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> dep(n);
  for (int i = 1; i < n; i++) {
    dep[i] = dep[(i - 1) / 2] + 1;
  }
  vector<vector<int>> all(n);
  for (int i = 0; i < n; i++) {
    all[dep[i]].push_back(i);
  }
  for (int d = n - 1; d >= 0; d--) {
    for (int i : all[d]) {
      for (int v : vals[i]) {
        Solve(i, v);
      }
    }
    if (d + 1 < n) {
      for (int i : all[d + 1]) {
        dp[i].clear();
        idx[i].clear();
      }
    }
  }
  vector<int> res;
  for (int i = 0; i < (int) vals[0].size(); i++) {
    if (vals[0][i] == a[0]) {
      res = dp[0][i];
    }
  }
  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 1 ms 348 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 1 ms 348 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 452 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 1 ms 348 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 452 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 7 ms 2012 KB Output is correct
15 Correct 5 ms 2140 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 1 ms 348 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 452 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 7 ms 2012 KB Output is correct
15 Correct 5 ms 2140 KB Output is correct
16 Correct 148 ms 44560 KB Output is correct
17 Correct 168 ms 44536 KB Output is correct
18 Correct 127 ms 44940 KB Output is correct
19 Correct 964 ms 144844 KB Output is correct
20 Correct 947 ms 143564 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 1 ms 348 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 452 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 7 ms 2012 KB Output is correct
15 Correct 5 ms 2140 KB Output is correct
16 Correct 148 ms 44560 KB Output is correct
17 Correct 168 ms 44536 KB Output is correct
18 Correct 127 ms 44940 KB Output is correct
19 Correct 964 ms 144844 KB Output is correct
20 Correct 947 ms 143564 KB Output is correct
21 Correct 856 ms 184948 KB Output is correct
22 Correct 771 ms 184928 KB Output is correct
23 Correct 822 ms 185904 KB Output is correct
24 Runtime error 594 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -