oj.uz

Submission #1002535

# Submission time Handle Problem Language Result Execution time Memory
1002535 2024-06-19T15:59:08 Z MilosMilutinovic Swap (BOI16_swap) C++14
48 / 100
 1000 ms 139212 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]);
  int total = 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());
    total += (int) vals[i].size();
  }
  assert(total <= n * 30);
  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]) {
        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 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 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 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 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 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 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 1112 KB Output is correct
12 Correct 5 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 7 ms 2136 KB Output is correct
15 Correct 7 ms 2140 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 1112 KB Output is correct
12 Correct 5 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 7 ms 2136 KB Output is correct
15 Correct 7 ms 2140 KB Output is correct
16 Correct 149 ms 44744 KB Output is correct
17 Correct 142 ms 44700 KB Output is correct
18 Correct 151 ms 45024 KB Output is correct
19 Execution timed out 1032 ms 139212 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 1112 KB Output is correct
12 Correct 5 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 7 ms 2136 KB Output is correct
15 Correct 7 ms 2140 KB Output is correct
16 Correct 149 ms 44744 KB Output is correct
17 Correct 142 ms 44700 KB Output is correct
18 Correct 151 ms 45024 KB Output is correct
19 Execution timed out 1032 ms 139212 KB Time limit exceeded
20 Halted 0 ms 0 KB -