QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #621043 | #7778. Turning Permutation | cpismylifeOwO | WA | 0ms | 3752kb | C++20 | 4.6kb | 2024-10-08 01:02:07 | 2024-10-08 01:02:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int MaxN = 5e1 + 5;
int n;
long long k;
void Inp()
{
cin >> n >> k;
}
bool isup[MaxN];
bool mark[MaxN];
int res[MaxN];
long long C[MaxN][MaxN];
long long F[2][MaxN];
long long Calc(int cur)
{
long long res = 1;
for (int x = 1; x <= n; x++)
{
if (mark[x])
{
continue;
}
int y = x;
while (y <= n && !mark[y])
{
y++;
}
if (F[isup[x]][y - x] > 1e18 || C[y - x][cur] > 1e18 || 1e18 / F[isup[x]][y - x] < C[y - x][cur])
{
return 1e18 + 1;
}
if (res > 1e18 || 1e18 / res < (F[isup[x]][y - x] * C[y - x][cur]))
{
return 1e18 + 1;
}
res *= F[isup[x]][y - x] * C[y - x][cur];
cur -= y - x;
x = y - 1;
}
return res;
}
bool Check(int x)
{
if (isup[x])
{
return (!mark[x] && mark[x - 1] && mark[x + 1]);
}
return !mark[x];
}
void Exc()
{
C[0][0] = 1;
for (int x = 1; x <= n; x++)
{
C[0][x] = C[0][x - 1];
for (int y = 1; y <= n; y++)
{
C[y][x] = min(C[y - 1][x - 1] + C[y][x - 1], (long long)1e18 + 1);
//cout << C[y][x] << " ";
}
//cout << "\n";
}
F[0][1] = 1;
F[0][0] = 1;
F[0][1] = 1;
F[1][1] = 1;
for (int x = 2; x <= n; x++)
{
F[0][x] = F[1][x - 1];
for (int y = 3; y < x; y += 2)
{
if (F[0][x] > 1e18 || F[0][y - 1] > 1e18 || F[1][x - y] > 1e18 || 1e18 / F[0][y - 1] < F[1][x - y])
{
F[0][x] = 1e18 + 1;
continue;
}
long long cur = F[0][y - 1] * F[1][x - y];
if (C[y - 1][x - 1] <= 1e18 && (cur != 0 || 1e18 / cur >= C[y - 1][x - 1]))
{
F[0][x] += cur * C[y - 1][x - 1];
}
else
{
F[0][x] = 1e18 + 1;
}
//cout << cur << " ";
if (F[0][x] > 1e18)
{
F[0][x] = 1e18 + 1;
}
}
if (x & 1)
{
F[0][x] += F[0][x - 1];
}
F[0][x] = min(F[0][x], (long long)1e18 + 1);
for (int y = 2; y < x; y += 2)
{
if (F[1][x] > 1e18 || F[1][y - 1] > 1e18 || F[1][x - y] > 1e18 || 1e18 / F[1][y - 1] < F[1][x - y])
{
F[1][x] = 1e18 + 1;
continue;
}
long long cur = F[1][y - 1] * F[1][x - y];
if (C[y - 1][x - 1] <= 1e18 && (cur != 0 || 1e18 / cur >= C[y - 1][x - 1]))
{
F[1][x] += cur * C[y - 1][x - 1];
}
else
{
F[1][x] = 1e18 + 1;
}
if (F[1][x] > 1e18)
{
F[1][x] = 1e18 + 1;
}
}
if (x % 2 == 0)
{
F[1][x] += F[1][x - 1];
}
F[1][x] = min(F[1][x], (long long)1e18 + 1);
//cout << F[0][x] << " " << F[1][x] << "\n";
}
if (F[0][n] + F[1][n] < k)
{
cout << -1;
return;
}
bool flip = false;
for (int x = 1; x <= n; x++)
{
long long cur1 = F[(x & 1) ^ 1][x - 1], cur2 = F[1][n - x], cur3 = C[x - 1][n - 1];
if (cur1 > 1e18 || cur2 > 1e18 || cur3 > 1e18 || 1e18 / cur1 < cur2 || 1e18 / (cur1 * cur2) < cur3 || k <= cur1 * cur2 * cur3)
{
res[1] = x;
mark[x] = true;
flip = (x & 1) ^ 1;
break;
}
k -= cur1 * cur2 * cur3;
}
mark[0] = mark[n + 1] = true;
for (int x = 1; x <= n; x++)
{
isup[x] = (x & 1) ^ flip ^ 1;
}
for (int x = 2; x <= n; x++)
{
for (int y = 1; y <= n; y++)
{
if (!Check(y))
{
continue;
}
mark[y] = true;
long long cur = Calc(n - x);
if (cur >= k)
{
res[x] = y;
break;
}
mark[y] = false;
k -= cur;
}
}
for (int x = 1; x <= n; x++)
{
cout << res[x] << " ";
}
}
int main()
{
//freopen("B.INP", "r", stdin);
//freopen("B.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
//cin >> test;
for (int x = 1; x <= test; x++)
{
Inp();
Exc();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3688kb
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: 3692kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
3 1
output:
1 3 2
result:
ok 3 number(s): "1 3 2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
3 10
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
3 52
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
3 756
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
3 7721
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
5 1
output:
1 3 2 5 4
result:
ok 5 number(s): "1 3 2 5 4"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 8
output:
2 4 1 3 5
result:
ok 5 number(s): "2 4 1 3 5"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 85
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
5 846
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
5 6957
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
8 1
output:
1 3 2 5 4 7 6 8
result:
ok 8 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
8 7
output:
1 3 2 5 7 8 4 6
result:
ok 8 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
8 71
output:
1 3 7 5 4 2 6 8
result:
ok 8 numbers
Test #18:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
8 863
output:
3 5 7 1 4 2 8 6
result:
ok 8 numbers
Test #19:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
8 7099
output:
-1
result:
ok 1 number(s): "-1"
Test #20:
score: -100
Wrong Answer
time: 0ms
memory: 3752kb
input:
10 100000
output:
0 0 0 0 0 0 0 0 0 0
result:
wrong answer 1st numbers differ - expected: '10', found: '0'