Submission #1162978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162978		avighna	Pancake (NOI12_pancake)	C++20	25 / 25	103 ms	1956 KiB

pancake

#include <bits/stdc++.h>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::function<int(int)> fact;
  fact = [&](int x) { return x == 0 ? 1 : x * fact(x - 1); };

  auto perm_to_num = [&](const std::vector<int> &x) {
    int s = 1, e = fact(x.size());
    std::vector<int> pos(x.size() + 1);
    std::iota(pos.begin(), pos.end(), 0);
    for (int i = 0; i < x.size(); ++i) {
      int size = fact(x.size() - i - 1);
      s += size * (pos[x[i]] - 1);
      e = s + size - 1;
      for (int j = x[i] + 1; j <= x.size(); ++j) {
        pos[j]--;
      }
    }
    return s;
  };
  auto num_to_perm = [&](int n, int x) {
    std::vector<int> ans;
    int s = 1, e = fact(n);
    std::vector<int> pos(n + 1);
    std::iota(pos.begin(), pos.end(), 0);
    for (int i = 0; i < n; ++i) {
      int size = fact(n - i - 1);
      for (int j = 1; j <= n; ++j) {
        int _s = s + size * (pos[j] - 1);
        int _e = _s + size - 1;
        if (_s <= x and x <= _e) {
          s = _s;
          e = _e;
          pos[j] = -100000;
          ans.push_back(j);
          break;
        }
      }
      for (int j = ans.back() + 1; j <= n; ++j) {
        pos[j]--;
      }
    }
    return ans;
  };

  std::vector ans(9, std::vector<int>(40321, 1000));
  for (int n = 1; n <= 8; ++n) {
    ans[n][fact(n)] = 0;
    std::queue<int> q;
    std::vector<bool> vis(40321);
    q.push(fact(n));
    while (!q.empty()) {
      auto node = q.front();
      q.pop();
      if (vis[node]) {
        continue;
      }
      vis[node] = true;
      auto a = num_to_perm(n, node);
      for (int i = 0; i < n; ++i) {
        std::reverse(a.begin() + i, a.end());
        auto nb = perm_to_num(a);
        if (ans[n][nb] > ans[n][node] + 1) {
          ans[n][nb] = ans[n][node] + 1;
          q.push(nb);
        }
        std::reverse(a.begin() + i, a.end());
      }
    }
  }

  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::cin >> n;
    std::vector<std::pair<int, int>> x(n);
    for (int i = 0; i < n; ++i) {
      std::cin >> x[i].first;
      x[i].second = i;
    }
    std::sort(x.begin(), x.end());
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
      a[x[i].second] = i + 1;
    }
    std::cout << ans[n][perm_to_num(a)] << '\n';
  }
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 8 / 8
• Subtask 5: 5 / 5