QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351948 | #5723. Carny Magician | Rong7 | AC ✓ | 1ms | 4396kb | C++14 | 3.3kb | 2024-03-12 17:26:49 | 2024-03-12 17:26:50 |
Judging History
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 '