QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293252 | #7778. Turning Permutation | ucup-team191# | WA | 0ms | 3680kb | C++23 | 1.4kb | 2023-12-29 02:44:50 | 2023-12-29 02:44:50 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
const int N=310,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;
int n;
ll k;
ll dp[N][N],cho[N][N],cn[N];
bool isk[N];
ll add(ll a,ll b)
{
return min(LLINF,a+b);
}
ll mul(ll a,ll b)
{
if (a>LLINF/b) return LLINF;
return a*b;
}
int getk(int c)
{
for (int i=0;;++i)
{
if (isk[i]) continue;
if (c==0)
{
isk[i]=1;
return i+1;
}
else --c;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for (int i=0;i<=n;++i)
{
cho[i][0]=1;
for (int j=1;j<=i;++j) cho[i][j]=add(cho[i-1][j-1],cho[i-1][j]);
}
dp[1][0]=1;
cn[1]=1;
cn[0]=1;
for (int i=2;i<=n;++i) for (int j=0;j<i;++j)
{
if (i%2)
{
for (int k=j;k<i-1;++k) dp[i][j]=add(dp[i][j],dp[i-1][k]);
}
else
{
for (int k=0;k<j;++k) dp[i][j]=add(dp[i][j],dp[i-1][k]);
}
cn[i]=add(cn[i],dp[i][j]);
}
--k;
while (n)
{
bool isp=0;
for (int p=0;p<n;++p)
{
ll kol=mul(cho[n-1][p],mul(cn[p],cn[n-1-p]));
if (k>=kol)
{
k-=kol;
continue;
}
cout<<getk(p)<<' ';
isp=1;
break;
}
if (!isp)
{
cout<<-1<<en;
exit(0);
}
--n;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3596kb
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: 3676kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3680kb
input:
3 1
output:
1 2 3
result:
wrong answer 2nd numbers differ - expected: '3', found: '2'