QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#445152#8529. Balance of Permutationucup-team1198#TL 2ms11036kbC++202.5kb2024-06-15 23:50:592024-06-15 23:50:59

Judging History

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

  • [2024-06-15 23:50:59]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:11036kb
  • [2024-06-15 23:50:59]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int N = 33;

__int128 dp[N][N][N][N * N];

__int128 calc_rest(vector<int> p, int n, int b) {

  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      for (int k = 0; k <= n; ++k)
        fill(dp[i][j][k], dp[i][j][k] + n * n, 0);
    }
  }


  int m = p.size();
  int bal = 0;
  int free = 0;
  vector<int> kek(n);
  vector<int> has_in(n);
  for (int i = 0; i < m; ++i) {
    ++has_in[p[i]];
    if (p[i] >= i) {
      --kek[p[i]];
      ++kek[i];
    } else {
      ++kek[p[i]];
      --kek[i];
    }
  }
  int sum = 0;
  for (int i = 0; i < m; ++i) {
    sum += bal;
    if (kek[i] > 0)
      bal += 1;
    if (kek[i] < -1)
      bal -= 1;
  }
  dp[m][bal][free][sum] = 1;
  for (int i = m; i < n; ++i) {
    for (int bal = 0; bal <= i; ++bal) {
      for (int free = 0; free <= bal; ++free) {
        for (int sum = 0; sum <= i * i; ++sum) {
          __int128 ans = dp[i][bal][free][sum];
          if (!ans)
            continue;
          if (has_in[i]) {
            if (bal > 0) {
              dp[i + 1][bal - 1][free][sum + bal] += ans * bal;
            }
            dp[i + 1][bal][free + 1][sum + bal] += ans;
          } else {
            if (bal > 0) {
              dp[i + 1][bal - 1][free - 1][sum + bal] += ans * bal * free;
            }
            dp[i + 1][bal + 1][free + 1][sum + bal] += ans;
            dp[i + 1][bal][free][sum + bal] += ans * (bal + free + 1);
          }
        }
      }
    }
  }
  return dp[n][0][0][b / 2];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int n, b;
  string s;
  cin >> n >> b >> s;
  __int128 k = 0;
  for (char c : s)
    k = k * 10 + int(c - '0');
  vector<int> ans;
  vector<bool> free(n, true);
  for (int i = 0; i < n; ++i) {
    ans.emplace_back();
    for (int j = 0; j < n; ++j) {
      if (free[j]) {
        ans[i] = j;
        auto cur = calc_rest(ans, n, b);
        if (cur < k) {
          k -= cur;
        } else {
          free[j] = false;
          break;
        }
      }
    }
  }
  for (int x : ans)
    cout << x + 1 << ' ';
  cout << '\n';
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11036kb

input:

6 6 6

output:

1 2 6 3 4 5 

result:

ok 6 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

30 300 3030303030303030303030

output:


result: