QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#302955 | #7778. Turning Permutation | ucup-team173# | WA | 1ms | 5868kb | C++17 | 4.0kb | 2024-01-11 16:04:11 | 2024-01-11 16:04:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) (int((x).size()))
typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define lll __int128_t
const int maxn=55;
int n;
lll k;
lll f[55][55][55][2];
const lll lim=2e18;
lll add(lll a,lll b){
return min(a+b,lim);
}
lll mul(lll a,lll b){
return min(lim,a*b);
}
void adto(lll&a,lll b){
a=min(lim,a+b);
}
int q[maxn];
lll calc(){
lll ans1=1,ans2=1;
//ji xiang xia
for(int i=1;i<n;i++){
if(q[i]&&q[i+1]){
if((i&1)&&q[i]<q[i+1]){
ans1=0;break;
}
if(!(i&1)&&q[i]>q[i+1]){
ans1=0;break;
}
}
}
for(int i=1,j;i<=n;i=j+1){
j=i;
if(q[i])continue;
while(j+1<=n&&q[j+1]==0)j++;
if(i==1){
if(j%2==0){
ans1=0;break;
}
ans1=mul(ans1,f[j][j][0][1]);
}
else if(j==n){
if(i%2==0){
ans1=0;break;
}
ans1=mul(ans1,f[j-i+1][j-i+1][0][n%2==0?0:1]);
}
else {
if(i%2==0||j%2==0){
ans1=0;break;
}
ans1=mul(ans1,f[j-i+1][j-i+1][0][1]);
}
}
for(int i=1;i<n;i++){
if(q[i]&&q[i+1]){
if((i&1)&&q[i]>q[i+1]){
ans2=0;break;
}
if(!(i&1)&&q[i]<q[i+1]){
ans2=0;break;
}
}
}
for(int i=1,j;i<=n;i=j+1){
j=i;
if(q[i])continue;
while(j+1<=n&&q[j+1]==0)j++;
if(i==1){
if(j%2==1){
ans2=0;break;
}
ans2=mul(ans2,f[j][j][0][1]);
}
else if(j==n){
if(i%2==1){
ans2=0;break;
}
ans2=mul(ans2,f[j-i+1][j-i+1][0][n%2==0?1:0]);
}
else {
if(i%2==1||j%2==1){
ans2=0;break;
}
ans2=mul(ans2,f[j-i+1][j-i+1][0][1]);
}
}
lll ans=add(ans1,ans2);
int cnt=0;
vector<int>v;
for(int i=1,j;i<=n;i=j+1){
j=i;
if(q[i])continue;
while(j+1<=n&&q[j+1]==0)j++;
v.pb(j-i+1);
cnt+=v.back();
}
vector<lll>vv;
for(int i=1;i<=cnt;i++)vv.pb(i);
for(lll i:v){
for(int j=1;j<=i;j++){
for(lll&o:vv){
if(o%j==0){
o/=j;break;
}
}
}
}
for(lll o:vv)ans=mul(ans,o);
return ans;
}
void solve() {
ll kll;
cin>>n>>kll;
kll--;
k=kll;
for(int len=1;len<=n;len++){
for(int j=0;j<len;j++){
f[len][1][j][0]=f[len][1][j][1]=1;
}
for(int i=1;i<=len;i++){
for(int j=0;j<=len;j++){
for(int w=0;w<j;w++){
adto(f[len][i+1][w][0],f[len][i][j][1]);
}
for(int w=j;w<len-i;w++){
adto(f[len][i+1][w][1],f[len][i][j][0]);
}
}
}
}
// cout<<(ll)add(f[n][n][0][0],f[n][n][0][1])<<"asdaf\n";
if(add(f[n][n][0][0],f[n][n][0][1])<k+1){
cout<<"-1";return;
}
vector<pair<int,int> >cur;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(q[j])continue;
q[j]=i;
lll tmp=calc();
if(k>=tmp)k-=tmp,q[j]=0;
else break;
}
}
vector<int>p(n+1);
for(int i=1;i<=n;i++){
p[q[i]]=i;
}
if(k!=0)cout<<"-1\n";
else
for(int i=1;i<=n;i++){
cout<<p[i]<<" \n"[i==n];
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5860kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5868kb
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: 5632kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
3 1
output:
1 3 2
result:
ok 3 number(s): "1 3 2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
3 10
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3 52
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3 756
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 7721
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 1
output:
1 3 2 5 4
result:
ok 5 number(s): "1 3 2 5 4"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
5 8
output:
2 4 1 3 5
result:
ok 5 number(s): "2 4 1 3 5"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
5 85
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 1ms
memory: 5584kb
input:
5 846
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
5 6957
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 1ms
memory: 5676kb
input:
8 1
output:
1 3 2 5 4 7 6 8
result:
ok 8 numbers
Test #16:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
8 7
output:
1 3 2 5 7 8 4 6
result:
ok 8 numbers
Test #17:
score: 0
Accepted
time: 1ms
memory: 5576kb
input:
8 71
output:
1 3 7 5 4 2 6 8
result:
ok 8 numbers
Test #18:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
8 863
output:
3 5 7 1 4 2 8 6
result:
ok 8 numbers
Test #19:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
8 7099
output:
-1
result:
ok 1 number(s): "-1"
Test #20:
score: -100
Wrong Answer
time: 1ms
memory: 5764kb
input:
10 100000
output:
5 9 3 7 1 10 8 6 2 4
result:
wrong answer 1st numbers differ - expected: '10', found: '5'