QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#280769 | #7778. Turning Permutation | ucup-team135# | WA | 0ms | 3612kb | C++20 | 3.7kb | 2023-12-09 17:53:24 | 2023-12-09 17:53:25 |
Judging History
answer
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define app push_back
__int128 one=1;
__int128 ways[55][3];
__int128 c[55][55];
const int inf=2e18;
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
for(int i=0;i<55;++i)
{
for(int j=0;j<=i;++j)
{
if(i==0 || i==j) c[i][j]=1;
else c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}
ways[0][0]=1;ways[0][1]=1;ways[0][2]=1;
for(int i=1;i<55;++i)
{
for(int l=0;l<i;++l)
{
ways[i][0]+=min(ways[l][1]*one*ways[i-l-1][1],one*inf)*one*c[i-1][l];
ways[i][0]=min(ways[i][0],one*inf);
if(l!=0 || (i==1)) ways[i][1]+=min(ways[l][2]*one*ways[i-l-1][1],one*inf)*c[i-1][l];
ways[i][1]=min(ways[i][1],one*inf);
if((l!=0 && (i-l-1)!=0) || (i==1)) ways[i][2]+=min(ways[l][2]*one*ways[i-l-1][2],one*inf)*c[i-1][l];
ways[i][2]=min(ways[i][2],one*inf);
}
}
/*vector<int> v(10);iota(v.begin(),v.end(),0LL);
int answ=0;
do {
bool ok=1;
for(int i=0;i<v.size()-2;++i)
{
if(v[i]>v[i+1] && v[i+1]>v[i+2]) ok=0;
if(v[i]<v[i+1] && v[i+1]<v[i+2]) ok=0;
}
answ+=ok;
}while(next_permutation(v.begin(),v.end()));
cout<<answ<<" answ "<<endl;
for(int i=1;i<55;++i)
{
for(int j=0;j<3;++j)
{
cout<<i<<" i "<<j<<" j "<<(int) (ways[i][j])<<" ways "<<endl;
}
}*/
int n,k;cin>>n>>k;
auto go2=[&](vector<pair<int,int> > zxc1)->int
{
vector<int> zxc;for(auto [l,r]:zxc1) zxc.app(r-l);
int s= accumulate(all(zxc),0LL);
__int128 res=1;
for(int i:zxc)
{
res*=c[s][i];res=min(res,one*inf);s-=i;
}
return res;
};
auto go=[&](vector<int> a)->int
{
vector<int> b(n);fill(all(b),n);
for(int i=0;i<n;++i)
{
if(a[i]!=(-1)) b[a[i]]=i;
}
for(int i=0;i<n-2;++i)
{
if(b[i]>b[i+1] && b[i+1]>b[i+2]) return 0;
if(b[i]<b[i+1] && b[i+1]<b[i+2]) return 0;
}
int le=(-1);
vector<pair<int,int> > zxc;
for(int i=0;i<n;++i)
{
if(b[i]!=n)
{
if(le!=(-1))
{
zxc.app({le,i});
}
le=(-1);continue;
}
else
{
if(le==(-1))
{
le=i;
}
}
}
if(le!=(-1)) zxc.app({le,n});
__int128 res=1;
for(auto [l,r]:zxc)
{
int cnt=2-(l==0)-(r==n);
res*=ways[r-l][cnt];res=min(res,one*inf);
}
res*=go2(zxc);res=min(res,one*inf);
return res;
};
vector<int> a(n);fill(all(a),-1);
//cout<<go(a)<<" go "<<endl;
if(go(a)>k)
{
cout<<(-1);return 0;
}
int cf=0;
bool ok=0;
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
if(!count(a.begin(),a.end(),j))
{
a[i]=j;
int cf1=cf+go(a);
if(cf1>=k)
{
ok=1;
break;
}
else
{
cf=cf1;
}
}
}
if(!ok) break;
}
if(ok)
{
for(int x:a) cout<<x+1<<' ';
}
else
{
cout<<(-1);
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3612kb
input:
3 2
output:
-1
result:
wrong answer 1st numbers differ - expected: '2', found: '-1'