QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252330 | #7778. Turning Permutation | Lynkcat# | WA | 1ms | 3896kb | C++20 | 3.8kb | 2023-11-15 18:24:47 | 2023-11-15 18:24:47 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N
using namespace std;
const int inf=1e18,N=255;
int cc[N][N],ans[N],bl;
int n,m;
int f[N],h[N];
inline int mul(int x,int y)
{
if (x==0||y==0) return 0;
if (inf/y<x) return inf;
return x*y;
}
inline int add(int x,int y)
{
return min(inf,x+y);
}
inline int C(int x,int y)
{
if (x<y||y<0) return 0;
return cc[x][y];
}
struct node
{
int l,r,v;
};
vector<node>g;
void dfs(int k)
{
if (k>n)
{
if (m>1)
{
cout<<"-1\n";
return;
}
for (int i=1;i<=n;i++) cout<<ans[i]<<" ";
cout<<'\n';
return;
}
for (auto U:g)
{
int l=U.l,r=U.r,v=U.v;
for (int i=l;i<=r;i++)
if ((i-l)%2==v||r-l+1==1)
{
int x=i-l;
int y=r-i;
int coef=1,tot=0;
if (x)
{
coef=mul(coef,C(tot+x,tot)),tot+=x;
coef=mul(coef,h[x]);
}
if (y)
{
coef=mul(coef,C(tot+y,tot)),tot+=y;
coef=mul(coef,h[y]);
}
for (auto V:g)
{
int L=V.l,R=V.r;
if (L!=l)
{
coef=mul(coef,C(tot+R-L+1,tot)),tot+=R-L+1;
coef=mul(coef,h[R-L+1]);
}
}
// cout<<"????"<<i<<" "<<m<<" "<<coef<<endl;
if (coef<m)
{
m-=coef;
continue;
} else
{
vector<node>nxt;
for (auto V:g)
if (V.l!=l) nxt.push_back(V);
if (x)
{
nxt.push_back((node){l,i-1,v});
}
if (y)
{
nxt.push_back((node){i+1,r,1});
}
nxt.swap(g);
ans[k]=i;
dfs(k+1);
return;
}
}
}
cout<<"-1\n";
return;
}
void BellaKira()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
int coef=mul(C(i-1+n-i,i-1),mul(h[i-1],h[n-i]));
// cout<<i<<" "<<m<<" "<<coef<<endl;
if (m>coef)
{
m-=coef;
} else
{
ans[1]=i;
if (i-1)
g.push_back((node){1,i-1,(i-1)%2});
if (n-i)
g.push_back((node){i+1,n,1});
dfs(2);
return;
}
}
dfs(1);
}
signed main()
{
cc[0][0]=1;
for (int i=1;i<=200;i++)
{
cc[i][0]=1;
for (int j=1;j<=i;j++)
{
cc[i][j]=cc[i-1][j-1]+cc[i-1][j];
cc[i][j]=min(cc[i][j],inf);
}
}
h[0]=1;
f[1]=1;h[1]=1;
for (int i=2;i<=200;i++)
{
f[i]=h[i-1];
for (int j=1;j+1<i;j++)
f[i]=add(f[i],mul(C(j,i-1-j),mul(f[j],h[i-1-j])));
for (int j=1;j<i;j+=2)
h[i]=add(h[i],mul(C(j,i-1-j),mul(h[j],h[i-1-j])));
}
// return 0;
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3748kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
4 6
output:
3 1 2 4
result:
ok 4 number(s): "3 1 2 4"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
3 1
output:
1 3 2
result:
ok 3 number(s): "1 3 2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
3 10
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
3 52
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
3 756
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
3 7721
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
5 1
output:
1 3 2 5 4
result:
ok 5 number(s): "1 3 2 5 4"
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3796kb
input:
5 8
output:
3 1 2 5 4
result:
wrong answer 1st numbers differ - expected: '2', found: '3'