QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#279780 | #7778. Turning Permutation | ucup-team2279# | WA | 0ms | 4036kb | C++20 | 2.0kb | 2023-12-09 09:03:32 | 2023-12-09 09:03:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mk make_pair
#define lowbit(x) (x&(-x))
#define pb emplace_back
#define pr pair<int,int>
#define let const auto
#define all(A) A.begin(),A.end()
void chkmin(int &x,int y){x=min(x,y);}
void chkmax(int &x,int y){x=max(x,y);}
const int N=55;
int read(){
int x=0,f=1; char c=getchar();
while(('0'>c||c>'9')&&c!='-') c=getchar();
if(c=='-') f=0,c=getchar();
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?x:-x;
}
ll f[N][2][2],C[N][N];
int n; ll k;
void mul(ll &t,ll p){
t=min((__int128)k,(__int128)t*p);
}
ll calc(vector <pr> range,int i){
auto get = [&](int l,int r){
return f[r-l+1][l!=1][r!=n];
};
ll ans=1; int rn=-1;
for(auto [l,r]:range) rn+=r-l+1;
for(auto [l,r]:range){
if(i>=l&&i<=r) mul(ans,get(l,i-1)),mul(ans,get(i+1,r)),mul(ans,C[rn][i-l]),mul(ans,C[rn-=i-l][r-i]),rn-=r-i;
else mul(ans,get(l,r)),mul(ans,C[rn][r-l+1]);
}
return ans;
}
vector <pr> cancel(vector <pr> t,int i){
vector <pr> s;
for(auto [l,r]:t){
if(i>=l&&i<=r){
if(i>l) s.pb(l,i-1);
if(i<r) s.pb(i+1,r);
}
else s.pb(l,r);
}
return s;
}
void print(vector <pr> range,ll res){
vector <int> g(n+1,0);
for(auto [l,r]:range){
if(l==r) g[l]=1;
for(int i=l+(l>1); i<=r-(r<n); i++) g[i]=1;
}
for(int i=1; i<=n; i++) if(g[i]){
ll val=calc(range,i);
if(res<=val) return printf("%d ",i),print(cancel(range,i),res);
res-=val;
}
}
int main(){
cin>>n>>k;
for(int i:{0,1})
for(int j:{0,1}) f[0][i][j]=f[1][i][j]=1;
for(int i=0; i<=n; i++){
C[i][0]=1;
for(int j=1; j<=i; j++) C[i][j]=min(k,C[i-1][j-1]+C[i-1][j]);
}
for(int i=2; i<=n; i++){
for(int j:{0,1})
for(int p:{0,1}){
for(int t=j+1; t<=i-p; t++)
f[i][j][p]=min(k,f[i][j][p]+(ll)min((__int128)k,min((__int128)k,(__int128)f[t-1][j][1]*f[i-t][1][p])*C[i-1][t-1]));
}
}
if(f[n][0][0]<k) return puts("-1"),0;
vector <pr> s={{1,n}};
print(s,k);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3812kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3848kb
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: 3620kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
3 1
output:
1 3 2
result:
ok 3 number(s): "1 3 2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
3 10
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3 52
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3 756
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 7721
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 4036kb
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: 3740kb
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: 3556kb
input:
5 85
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
5 846
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5 6957
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
8 1
output:
1 3 2 5 4 7 6 8
result:
ok 8 numbers
Test #16:
score: -100
Wrong Answer
time: 0ms
memory: 4036kb
input:
8 7
output:
1 3 2 5 7 6 4 8
result:
wrong answer 6th numbers differ - expected: '8', found: '6'