QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#280899#7778. Turning Permutationucup-team1191#WA 0ms3868kbC++233.4kb2023-12-09 18:20:042023-12-09 18:20:04

Judging History

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

  • [2023-12-09 18:20:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3868kb
  • [2023-12-09 18:20:04]
  • 提交

answer

#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
typedef long long ll;

const ll Inf = (ll)1e18 + 7;

const int N = 50;

ll dp[N][2][2]; // 1 - up, 0 - down

ll safe_mul(ll a, ll b) {
  if (b == 0)
    return 0;
  if (a > Inf / b) {
    return Inf;
  }
  return min(Inf, a * b);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  ll k;
  cin >> n >> k;
  --k;
  vector<vector<ll>> C(n + 1, vector<ll>(n + 1));
  for (int i = 0; i <= n; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
      C[i][j] = min(C[i][j], Inf);
    }
  }
  dp[1][0][1] = dp[1][1][0] = 1;
  for (int len = 2; len <= n; ++len) {
    for (int lf = 0; lf <= 1; ++lf) {
      for (int rg = 0; rg <= 1; ++rg) {
        for (int pos = 0; pos < len; ++pos) {
          if (pos == 0 && lf == 0)
            continue;
          if (pos == len - 1 && rg == 1)
            continue;
          ll ways = 1;
          int lf_sz = pos;
          int rg_sz = len - pos - 1;
          if (lf_sz > 0)
            ways = safe_mul(ways, dp[lf_sz][lf][1]);
          if (rg_sz > 0)
            ways = safe_mul(ways, dp[rg_sz][0][rg]);
          ways = safe_mul(ways, C[lf_sz + rg_sz][lf_sz]);
          dp[len][lf][rg] += ways;
          dp[len][lf][rg] = min(dp[len][lf][rg], Inf);
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int lf = 0; lf <= 1; ++lf) {
      for (int rg = 0; rg <= 1; ++rg) {
        // cout << i << ' ' << lf << ' ' << rg << ' ' << dp[i][lf][rg] << endl;
      }
    }
  }
  {
    ll tot = 0;
    for (int i = 0; i <= 1; ++i) {
      for (int j = 0; j <= 1; ++j) {
        tot += dp[n][i][j];
        tot = min(tot, Inf);
      }
    }
    if (tot <= k) {
      cout << "-1\n";
      return 0;
    }
  }

  vector<int> used(n), p(n), ip(n, -1);
  for (int i = 0; i < n; ++i) {
    auto calc_ways = [&]() {
      vector<int> lens;
      ll ways = 1;
      for (int l = 0; l < n; ++l) {
        if (ip[l] == -1) {
          int r = l;
          while (r < n && ip[r] == -1) {
            ++r;
          }
          --r;
          lens.push_back(r - l + 1);
          ll cur = 0;
          for (int lf = 0; lf <= 1; ++lf) {
            for (int rg = 0; rg <= 1; ++rg) {
              if (l != 0 && lf == 0)
                continue;
              if (r + 1 != n && rg == 1)
                continue;
              cur += dp[r - l + 1][lf][rg];
              cur = min(cur, Inf);
            }
          }
          ways = safe_mul(ways, cur);
          l = r;
        }
      }
      int rem = 0;
      for (auto l : lens) {
        rem += l;
        ways = safe_mul(ways, C[rem][l]);
      }
      return ways;
    };
    for (int j = 0; j < n; ++j) {
      if (used[j])
        continue;
      p[i] = j;
      ip[j] = i;
      used[j] = 1;
      ll ways = calc_ways();
      if (ways > k) {
        break;
      }
      k -= ways;
      p[i] = 0;
      ip[j] = -1;
      used[j] = 0;
    }
  }
  for (int i = 0; i < n; ++i) {
    cout << p[i] + 1 << ' ';
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3560kb

input:

3 2

output:

2 1 3 

result:

ok 3 number(s): "2 1 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

4 6

output:

3 1 2 4 

result:

ok 4 number(s): "3 1 2 4"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3792kb

input:

3 1

output:

1 2 3 

result:

wrong answer 2nd numbers differ - expected: '3', found: '2'