QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351948#5723. Carny MagicianRong7AC ✓1ms4396kbC++143.3kb2024-03-12 17:26:492024-03-12 17:26:50

Judging History

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

  • [2024-03-12 17:26:50]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4396kb
  • [2024-03-12 17:26:49]
  • 提交

answer

// Not afraid to dark.

#include <bits/stdc++.h>
using namespace std;

#define int long long

namespace io {
    int read_pos, read_dt; char read_char;
    inline int read (int &p = read_pos){
        p = 0, read_dt = 1; read_char = getchar ();
        while (! isdigit (read_char)){
            if (read_char == '-')
                read_dt = - 1;
            read_char = getchar ();
        }
        while (isdigit (read_char)){
            p = (p << 1) + (p << 3) + read_char - 48;
            read_char = getchar ();
        }
        return p = p * read_dt;
    }
    int write_sta[65], write_top;
    inline void write (int x){
        if (x < 0)
            putchar ('-'), x = - x;
        write_top = 0;
        do
            write_sta[write_top ++] = x % 10, x /= 10;
        while (x);
        while (write_top)
            putchar (write_sta[-- write_top] + 48);
    }
    int llen;
    inline int get_string (char c[], int &len = llen){
        len = 0;
        read_char = getchar ();
        while (read_char == ' ' || read_char == '\n' || read_char == '\r')
            read_char = getchar ();
        while (read_char != ' ' && read_char != '\n' && read_char != '\r'){
            c[++ len] = read_char;
            read_char = getchar ();
        }
        return len;
    }
}

const int N = 50, inf = 1e18 + 5;
int n, m, k;
int dp[N + 5][N + 5][N + 5];
int C[N + 5][N + 5];

inline int mul (int x, int y){
    if (! x || ! y)
        return 0;
    if (inf / y < x)
        return inf;
    return x * y;
}
inline int add (int x, int y){
    if (inf - y < x)
        return inf;
    return x + y;
}

int ans[N + 5];
bool vis[N + 5];

signed main (){
    io::read (n), io::read (m), io::read (k);
    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] = add (C[i - 1][j], C[i - 1][j - 1]);
    }
    dp[0][0][0] = 1;
    int jc = 1;
    for (int l = 1;l <= n;++ l){
        jc *= l;
        for (int i = 0;i <= l;++ i){
            if (l > 20 || (l == 20 && i >= 3))
                dp[l][i][0] = inf;
            else {
                dp[l][i][0] = jc;
                for (int j = 1;j <= l - i;++ j)
                    dp[l][i][0] -= C[l - i][j] * dp[l - j][i][0];
            }
            for (int j = 1;j <= l;++ j)
                if (j > l - i)
                    dp[l][i][j] = 0;
                else
                    dp[l][i][j] = mul (C[l - i][j], dp[l - j][i][0]);
        }
    }
    for (int p = 1, res;p <= n;++ p){
        res = 0;
        int i;
        for (i = 1;i <= n;++ i){
            if (m == 0 && i == p)
                continue;
            if (vis[i])
                continue;
            int cnt = 0, rlt;
            for (int j = p + 1;j <= n;++ j)
                if (vis[j] || i == j)
                    ++ cnt;
            rlt = res + dp[n - p][cnt][m - (i == p)];
            if (rlt >= k)
                goto found;
            res = rlt;
        }
        return puts ("-1"), 0;
        found : ;
        ans[p] = i;
        vis[i] = true;
        k -= res;
        if (i == p)
            -- m;
    }
    for (int i = 1;i <= n;++ i)
        io::write (ans[i]), putchar (' ');
    puts ("");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 1 1

output:

1 3 2 

result:

ok single line: '1 3 2 '

Test #2:

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

input:

3 2 1

output:

-1

result:

ok single line: '-1'

Test #3:

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

input:

5 3 7

output:

2 1 3 4 5 

result:

ok single line: '2 1 3 4 5 '

Test #4:

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

input:

49 2 531768966090517377

output:

1 2 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 41 37 33 38 31 46 40 32 44 47 42 45 35 36 48 49 29 34 43 39 

result:

ok single line: '1 2 4 3 6 5 8 7 10 9 12 11 14 ... 42 45 35 36 48 49 29 34 43 39 '

Test #5:

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

input:

32 9 769470542992117121

output:

1 2 3 4 5 6 7 8 9 11 10 13 29 20 32 19 18 27 31 12 26 30 22 25 17 28 24 16 14 23 15 21 

result:

ok single line: '1 2 3 4 5 6 7 8 9 11 10 13 29 ... 22 25 17 28 24 16 14 23 15 21 '

Test #6:

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

input:

49 14 894400542924763905

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 49 29 43 47 44 41 39 36 42 46 31 33 37 38 40 32 35 48 45 34 

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 31 33 37 38 40 32 35 48 45 34 '

Test #7:

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

input:

7 6 1

output:

-1

result:

ok single line: '-1'

Test #8:

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

input:

26 22 1

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 23 26 25 

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 17 18 19 20 21 22 24 23 26 25 '

Test #9:

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

input:

41 22 42931473586776961

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 41 28 34 35 40 39 24 37 30 23 36 26 27 33 31 29 25 32 38 

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 23 36 26 27 33 31 29 25 32 38 '

Test #10:

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

input:

10 9 1

output:

-1

result:

ok single line: '-1'

Test #11:

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

input:

3 2 1

output:

-1

result:

ok single line: '-1'

Test #12:

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

input:

20 9 26243474

output:

1 2 3 4 5 6 7 8 10 18 16 14 15 17 12 13 19 11 9 20 

result:

ok single line: '1 2 3 4 5 6 7 8 10 18 16 14 15 17 12 13 19 11 9 20 '

Test #13:

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

input:

32 27 75

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 28 31 29 32 30 27 

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 23 24 25 26 28 31 29 32 30 27 '

Test #14:

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

input:

19 13 515

output:

1 2 3 4 5 6 7 8 9 10 11 12 14 19 17 13 15 18 16 

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 14 19 17 13 15 18 16 '

Test #15:

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

input:

34 3 981736676158966785

output:

1 2 3 5 4 7 6 9 8 11 10 13 12 16 14 32 33 31 21 27 20 19 15 30 17 24 29 26 25 23 28 34 18 22 

result:

ok single line: '1 2 3 5 4 7 6 9 8 11 10 13 12 ... 17 24 29 26 25 23 28 34 18 22 '

Test #16:

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

input:

22 1 971652343027876993

output:

1 4 2 16 20 22 3 21 6 14 9 15 18 11 10 17 19 12 8 5 7 13 

result:

ok single line: '1 4 2 16 20 22 3 21 6 14 9 15 18 11 10 17 19 12 8 5 7 13 '