QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601333 | #7778. Turning Permutation | argtarg | WA | 0ms | 3484kb | C++20 | 4.0kb | 2024-09-29 22:24:09 | 2024-09-29 22:24:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define ll long long
#define endl '\n'
#define pii pair<int, int>
void solve();
void init();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
init();
while (T--) {
solve();
}
return 0;
}
const int N = 51;
int C[N][N];
void init() {
for(int i=0;i<N;i++) {
C[i][0]=1;
}
// int mi=0;
for(int i=1;i<N;i++) {
for(int j=1;j<=i;j++) {
C[i][j]=C[i-1][j-1]+C[i-1][j];
// cout<<C[i][j]<<' ';
// mi=min(mi,C[i][j]);
}
// cout<<endl;
}
// cout<<mi<<endl;
}
void solve() {
ll ni,numi;
cin>>ni>>numi;
int n,num;
// cin>>n>>num;
n=ni;
num=numi;
vector<int>p(n+2);
p[n+1]=n+1;
vector<vector<int>>dp(n+1,vector<int>(n+1));
vector<int>sum1(n+1);
sum1[1]=sum1[0]=1;
sum1[2]=2;
int ttt=1;
for(int i=3;i<=n;i++) {
for(int j=1;j<=i;j++) {
int l=j-1,r=i-j;
dp[i][j]=C[l+r][l]*max(ttt,sum1[l]/2)*max(ttt,sum1[r]/2);
sum1[i]+=dp[i][j];
// if(i==3)cout<<dp[i][j]<<' ';
}
}
// cout<<sum1[3]<<endl;
for(int i=1;i<=n;i++) {
int ok=0;
for(int j=1;j<=n;j++) {
if(p[j]!=0)continue;
int ook=1;
p[j]=i;
for(int k=max(j-2,ttt);k<=j;k++) {
if(k+2>n)continue;
int ok=0;
for(int q=k;q<=k+2;q++) {
if(p[q]==0)ok=1;
}
if(ok==1)continue;
if(p[k]<p[k+1]&&p[k+1]<p[k+2]||p[k]>p[k+1]&&p[k+1]>p[k+2]) {
ook=0;
}
}
for(int k=1;k<=n;k++) {
if(p[k]==0) {
if(k>=3) {
if(p[k-2]!=0&&p[k-1]!=0&&p[k-1]>p[k-2])ook=0;
}
if(k+2<=n) {
if(p[k+2]!=0&&p[k+1]!=0&&p[k+1]>p[k+2])ook=0;
}
}
}
p[j]=0;
if(ook==0)continue;
/*if(i==3) {
cout<<"this"<<endl;
}*/
p[j]=i;
int l=0;
int tmp=1;
int okk=1;
int sum=n-i;
for(int k=1;k<=n+1;k++) {
if(p[k]!=0) {
if(!(l==0||k==n+1)) {
if(k-1-l!=0&&(k-1-l)&1^1) {
ok=0;
tmp=0;
break;
}
}
int c=C[sum][k-l-1]*max(ttt,sum1[k-l-1]/2);
// if(i*j==1)cout<<"c== "<<c<<endl;
if((num+c-1)/c<=tmp||ok==1||C[sum][k-l-1]*tmp>=num||tmp*(sum1[k-l-1]/2)>=num
||C[sum][k-l-1]>=tmp||C[sum][k-l-1]<0||C[sum][k-l-1]*tmp<0||
(sum1[k-l-1]/2)<0||(sum1[k-l-1]/2)*tmp<0||(sum1[k-l-1]/2)>=num) {
ok=1;
}
else {
tmp*=c;
// if(i==4&&j==5)cout<<(ll)C[sum][k-l-1]<<' '<<(ll)sum1[k-l-1]/2<<endl;?
sum-=(k-1-l);
}
l=k;
}
}
// cout<<"i== "<<(ll)i;
// cout<<" j== "<<(ll)j;
// cout<<" ok== "<<(ll)ok<<endl;
if(ok==1)break;
p[j]=0;
num-=tmp;
// cout<<" tmp== "<<(ll)tmp<<endl;
}
if(ok==0) {
// cout<<"-1 "<<i<<endl;
cout<<-1<<endl;
return;
}
}
vector<int>pos(n+1);
for(int i=1;i<=n;i++) {
pos[p[i]]=i;
}
for(int i=1;i<=n;i++) {
cout<<(ll)pos[i]<<' ';
}
cout<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3484kb
input:
3 2
output:
1 3 2
result:
wrong answer 1st numbers differ - expected: '2', found: '1'