QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#290922#7778. Turning PermutationyllcmWA 1ms3924kbC++142.3kb2023-12-25 20:59:442023-12-25 20:59:45

Judging History

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

  • [2023-12-25 20:59:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3924kb
  • [2023-12-25 20:59:44]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
#define int long long
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int INF = 1e18;
const int N = 55;
int n, k;
int f[N][N][2], g[N][2], C[N][N];
void init() {
  C[0][0] = 1;
  for(int i = 1; i < N; i++) {
    C[i][0] = 1;
    for(int j = 1; j <= i; j++) {
      C[i][j] = min(INF + 1, C[i - 1][j] + C[i - 1][j - 1]);
    }
  }
  f[1][1][0] = f[1][1][1] = 1;
  for(int i = 2; i < N; i++) {
    for(int j = 1; j <= i - 1; j++) {
      for(int o = 0; o < 2; o++) {
        for(int k = 1; k <= i; k++) {
          if((o == 0 && k > j) || (o == 1 && k <= j))continue;
          f[i][k][o] = min(INF + 1, f[i][k][o] + f[i - 1][j][o ^ 1]);
        }
      }
    }
  }
  for(int i = 1; i < N; i++) {
    for(int o = 0; o < 2; o++) {
      for(int j = 1; j <= i; j++) {
        g[i][o] = min(INF + 1, g[i][o] + f[i][j][o]);
      }
    }
  }
  return ;
}
int p[N], q[N];
int calc() {
  int o = (p[1] & 1);
  for(int i = 1; i < n; i++) {
    if(!~q[i] || !~q[i + 1])continue;
    if((q[i] > q[i + 1]) != ((i ^ p[1]) & 1))return 0;
  }
  int sum = 0, res = 1;
  auto mul = [&](int x, int y) {return x && y && x > INF / y ? INF + 1 : x * y;};
  for(int i = 1; i <= n; i++) {
    if(~q[i])continue;
    int k = i;
    while(k < n && !~q[k + 1])k++;
    res = mul(mul(res, g[k - i + 1][(i ^ p[1]) & 1]), C[sum + k - i + 1][sum]);
    sum += k - i + 1; i = k;
  }
  return res;
}
signed main() {
  init();
  n = read(); k = read(); 
  for(int i = 1; i <= n; i++)q[i] = -1;
  int all = min(INF + 1, g[n][0] + g[n][1]);
  if(all < k)return puts("-1"), 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      if(~q[j])continue;
      p[i] = j; q[j] = i;
      int val = calc();
      if(val >= k)break;
      else k -= val, q[j] = -1;
    }
  }
  if(k > 1)return puts("-1");
  for(int i = 1; i <= n; i++)printf("%lld ", p[i]); putchar('\n');
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3856kb

input:

3 2

output:

2 1 3 

result:

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

Test #2:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 1ms
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: 3744kb

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

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

input:

3 1

output:

1 2 3 

result:

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