oj.uz

Submission #1002565

# Submission time Handle Problem Language Result Execution time Memory
1002565 2024-06-19T16:12:34 Z MilosMilutinovic Swap (BOI16_swap) C++14
68 / 100
 462 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<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);
  }
  vector<vector<int>> vals(n);
  function<void(int, int)> Update = [&](int i, int v) {
    int L = i * 2 + 1, R = i * 2 + 2;
    if (L >= n) {
      return;
    }
    if (R >= n) {
      if (v < a[L]) {
        vals[L].push_back(a[L]);
      } else {
        vals[L].push_back(v);
      }
      return;
    }
    if (v <= a[L] && v <= a[R]) {
      vals[L].push_back(a[L]);
      vals[R].push_back(a[R]);
    } else if (a[L] <= v && a[L] <= a[R]) {
      vals[L].push_back(v);
      vals[R].push_back(a[R]);
    } else {
      vals[L].push_back(a[L]);
      vals[R].push_back(v);
      vals[L].push_back(v);
      vals[R].push_back(a[L]);
    }
  };
  vals[0].push_back(a[0]);
  for (int d = 0; d < n; d++) {
    for (int i : all[d]) {
      sort(vals[i].begin(), vals[i].end());
      vals[i].erase(unique(vals[i].begin(), vals[i].end()), vals[i].end());
      for (int v : vals[i]) {
        Update(i, v);
      }
    }
  }
  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];
  };
  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]) {
        vector<vector<int>>{}.swap(dp[i]);
        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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 344 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 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 344 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 2 ms 1112 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 3 ms 1664 KB Output is correct
15 Correct 4 ms 1628 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 344 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 2 ms 1112 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 3 ms 1664 KB Output is correct
15 Correct 4 ms 1628 KB Output is correct
16 Correct 72 ms 33220 KB Output is correct
17 Correct 69 ms 32716 KB Output is correct
18 Correct 78 ms 33548 KB Output is correct
19 Correct 372 ms 117304 KB Output is correct
20 Correct 361 ms 116232 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 344 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 2 ms 1112 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 3 ms 1664 KB Output is correct
15 Correct 4 ms 1628 KB Output is correct
16 Correct 72 ms 33220 KB Output is correct
17 Correct 69 ms 32716 KB Output is correct
18 Correct 78 ms 33548 KB Output is correct
19 Correct 372 ms 117304 KB Output is correct
20 Correct 361 ms 116232 KB Output is correct
21 Correct 369 ms 138224 KB Output is correct
22 Correct 376 ms 138740 KB Output is correct
23 Correct 358 ms 139996 KB Output is correct
24 Runtime error 462 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -