QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #641444 | #7778. Turning Permutation | SCAU_xyjkanade | WA | 0ms | 3736kb | C++17 | 2.2kb | 2024-10-14 20:31:41 | 2024-10-14 20:31:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 60;
int n;
long long k;
int ans[N];
long long dp[N][N];
int vis[N];
int fx;
int fir ;
long long sol(int bg) // the begin dp position [bg,n]
{
if(!fx)
{
if(fir % 2 == 1)fx = 1;
else fx = 2;
}
long long ret = 0;
int cnt = 0;
memset(dp,0,sizeof(dp));
if(fx == 1)///偶数在奇数右边
{
for(int i = 1;i <= n;i++)
{
if(vis[i])continue;
++cnt;
if(cnt == 1)
{
for(int j = 1;j <= n - bg + 1;j++)
dp[cnt][j] = 1;
}
if(vis[i - 1])
{
for(int j = 1;j <= n - bg + 1 - cnt + 1;j++)
{
for(int k = 1;k <= n - bg + 1 - cnt + 2;k++)
{
dp[cnt][j] += dp[cnt - 1][k];
}
}
}
else
for(int j = 1;j <= n - bg + 1 - cnt + 1;j++)//dp[cnt][j]
{
if(i % 2 == 1)
{
for(int k = j + 1;k <= n - bg + 1 - cnt + 2;k++)
dp[cnt][j] += dp[cnt - 1][k];
}
else
{
for(int k = 1;k <= j;k++)
dp[cnt][j] += dp[cnt - 1][k];
}
}
}
}
else if(fx == 2)///偶数在奇数右边
{
for(int i = 1;i <= n;i++)
{
if(vis[i])continue;
++cnt;
if(vis[i - 1])
{
for(int j = 1;j <= n - bg + 1 - cnt + 1;j++)
{
for(int k = 1;k <= n - bg + 1 - cnt + 2;k++)
{
dp[cnt][j] += dp[cnt - 1][k];
}
}
}
else
for(int j = 1;j <= n - bg + 1 - cnt + 1;j++)//dp[cnt][j]
{
if(i % 2 == 0)
{
for(int k = j + 1;k <= n - bg + 1 - cnt + 2;k++)
dp[cnt][j] += dp[cnt - 1][k];
}
else
{
for(int k = 1;k <= j;k++)
dp[cnt][j] += dp[cnt - 1][k];
}
}
}
}
return dp[cnt][1];
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n;
cin >> k;
int flag = 1;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
if(vis[j]) continue;
if(i == 1)fir = j;
vis[j] = 1;
long long tt = sol(i + 1);
if(tt < k)k -= tt;
else
{
ans[i] = j;
flag = 0;
break;
}
vis[j] = 0;
}
if(i == 1 && flag == 1)
{
cout << -1;
return 0;
}
}
for(int i = 1;i <= n;i++)
{
if(ans[i])cout << ans[i] << " ";
else cout << n << " ";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
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: 3636kb
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: 3616kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3676kb
input:
3 1
output:
1 2 3
result:
wrong answer 2nd numbers differ - expected: '3', found: '2'