QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#446098#8529. Balance of Permutationucup-team3215TL 0ms0kbC++201.5kb2024-06-16 21:25:312024-06-16 21:25:31

Judging History

你现在查看的是最新测评结果

  • [2024-06-16 21:25:31]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-06-16 21:25:31]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;

u128 mem[30][30][30][256];
u16 mark[30][30][30][256], ct;

int n, b;

u128 cnt(int l, int c, int d, int b, u32 m) {
  if (b < c * (c - 1) / 2 || b > (n - l) * (n - l - 1) / 2 || max(c, d) + l > n) return 0;
  if (l == n - 1) return 1;
  if (mark[l][c][d][b] == ct) return mem[l][c][d][b];
  mark[l][c][d][b] = ct;
  u128 ans{};
  if ((m & 1 << l) && d) {
    ans += cnt(l + 1, c - 1, d - 1, b - c + 1, m) * c * d;
    ans += cnt(l + 1, c, d, b - c, m) * d;
  }
  if (c += m >> l & 1) ans += cnt(l + 1, c - 1, d, b - c + 1, m) * c;
  ans += cnt(l + 1, c, d + 1, b - c, m);
  return mem[l][c -= m >> l & 1][d][b] = ans;
}

u128 cnt(int l, int b, u32 m) {
  int c = 0;
  for (int i = 0; i < l; ++i) if (m & 1 << i) {
    ++c;
    b -= l - i;
    m ^= 1 << i;
  }
  ++ct;
  auto ans = cnt(l, c, 0, b, m);
  return ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> b; b /= 2;
  u128 k{};
  for (char c; cin >> c && isdigit(c); ) k = k * 10 + c - '0';
  u32 ans[30], l = 0, m = (1 << n) - 1;
  while (l < n) {
    for (int i = 0; i < n; ++i) if (m & 1 << i) if (auto t = cnt(l + 1, b - max((int)l - i, {}), m - (1 << i)); t >= k) {
      b -= max((int)l - i, {});
      ans[l++] = i + 1;
      m -= 1 << i;
      break;
    } else k -= t;
  }
  for (int i = 0; i < n; ++i) cout << ans[i] << ' ';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

6 6 6

output:


result: