QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#703393 | #7778. Turning Permutation | PandaGhost | WA | 1ms | 3860kb | C++17 | 5.0kb | 2024-11-02 17:42:32 | 2024-11-02 17:42:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using i128=__int128;
#define OPFI(x) freopen(#x".in", "r", stdin);\
freopen(#x".out", "w", stdout)
#define REP(i, a, b) for(int i=(a); i<=(b); ++i)
#define REPd(i, a, b) for(int i=(a); i>=(b); --i)
inline ll rd(){
ll r=0, k=1; char c; while(!isdigit(c=getchar())) if(c=='-') k=-k;
while(isdigit(c)) r=r*10+c-'0', c=getchar(); return r*k;
}
constexpr int N=50+10, M=25+10;
constexpr i128 MX=LLONG_MAX;
ll n, p[N];
i128 f[M][3], c[N][N], k, tmpsum[N];
struct node{
ll l, r, kk, ff;
bool operator<(const node& rhs) const {
return l<rhs.l;
}
};
set<node> g;
bool inset(int x){
for(auto [l, r, kk, ff]:g){
if(l<=x&&x<=r) return true;
}
return false;
}
i128 calc(int x){
i128 res=1;
int num=0;
for(auto [l, r, kk, ff]:g){
if(x<l||x>r){
num+=r-l+1;
i128 tmp=c[num][r-l+1]*f[kk][abs(ff)];
if(tmp>=MX) return MX;
res=res*tmp;
}else{
if(x>l){
// l, x-1, (x-l)/2, ff==1
num+=x-1-l+1;
i128 tmp=c[num][x-1-l+1]*f[(x-l)/2][ff==1];
if(tmp>=MX) return MX;
res=res*tmp;
if(res>=MX) return MX;
}
if(x<r){
// x+1, r, (r-x)/2, ff==-1
num+=r-x-1+1;
i128 tmp=c[num][r-x-1+1]*f[(r-x)/2][ff==-1];
if(tmp>=MX) return MX;
res=res*tmp;
if(res>=MX) return MX;
}
}
if(res>=MX) return MX;
}
return res;
}
void del(int x){
for(auto i=g.begin(); i!=g.end(); ++i){
if(i->l<=x&&x<=i->r){
ll tl=i->l, tr=i->r, ff=i->ff;
g.erase(i);
if(x>tl) g.insert((node){tl, x-1, (x-tl)/2, ff==1});
if(x<tr) g.insert((node){x+1, tr, (tr-x)/2, -(ff==-1)});
break;
}
}
}
int main(){
// OPFI(test1);
n=rd(), k=rd();
f[0][0]=f[0][1]=1;
c[0][0]=1;
REP(i, 1, 52){
c[i][0]=c[i][i]=1;
REP(j, 1, i-1){
c[i][j]=c[i-1][j]+c[i-1][j-1];
if(c[i][j]>=MX) c[i][j]=MX;
}
}
REP(k, 1, 26){
f[k][0]=0;
REP(i, 0, k-1){
i128 tmp=f[i][0]*f[k-1-i][0];
if(tmp>=MX){
f[k][0]=MX; break;
}
f[k][0]+=c[2*k][2*i+1]*f[i][0]*f[k-1-i][0];
if(f[k][0]>=MX){
f[k][0]=MX; break;
}
}
}
REP(k, 1, 26){
f[k][1]=0;
REP(i, 0, k-1){
i128 tmp=f[i][1]*f[k-1-i][0];
if(tmp>=MX){
f[k][1]=MX; break;
}
f[k][1]+=c[2*k-1][2*i]*f[i][1]*f[k-1-i][0];
if(f[k][1]>=MX){
f[k][1]=MX; break;
}
}
}
// cerr<<(ll)f[1][0]<<endl;
REP(i, 1, n){
if(i&1){
int tt=n-1+(n&1);
int x=(tt-i)/2, y=(i-1)/2;
// (x, (n&1)) (y, 1)
i128 tmp=f[x][n&1]*f[y][1];
if(tmp>=MX) tmpsum[i]=MX;
else{
tmpsum[i]=c[n-1][2*y]*tmp;
if(tmpsum[i]>=MX) tmpsum[i]=MX;
}
// cerr<<"i:"<<i<<" "<<(ll)tmpsum[i]<<endl;
}else{
int tt=n-(n&1);
int x=(tt-i)/2, y=(i-2)/2;
// (x, 1-(n&1)) (y, 0)
i128 tmp=f[x][1-(n&1)]*f[y][0];
if(tmp>=MX) tmpsum[i]=MX;
else{
tmpsum[i]=c[n-1][2*y+1]*tmp;
if(tmpsum[i]>=MX) tmpsum[i]=MX;
}
}
tmpsum[i]+=tmpsum[i-1];
if(tmpsum[i]>=MX) tmpsum[i]=MX;
// cerr<<(ll)tmpsum[i]<<" ";
if(tmpsum[i]>=k){
p[1]=i;
k-=tmpsum[i-1];
if(i&1){
int tt=n-1+(n&1);
int x=(tt-i)/2, y=(i-1)/2;
// (x, (n&1)) (y, 1)
if(i<n) g.insert((node){i+1, n, x, n&1});
if(i>1) g.insert((node){1, i-1, y, -1});
}else{
int tt=n-(n&1);
int x=(tt-i)/2, y=(i-2)/2;
// (x, 1-(n&1)) (y, 0)
if(i<n) g.insert((node){i+1, n, x, 1-(n&1)});
if(i>1) g.insert((node){1, i-1, y, 0});
}
break;
}
}
// cerr<<(ll)k<<endl;
if(!p[1]){
puts("-1");
return 0;
}
REP(i, 2, n){
memset(tmpsum, 0, sizeof(tmpsum));
REP(j, 1, n){
if(!inset(j)){
tmpsum[j]=tmpsum[j-1];
continue;
}
tmpsum[j]=calc(j);
tmpsum[j]+=tmpsum[j-1];
if(tmpsum[j]>=MX) tmpsum[j]=MX;
if(tmpsum[j]>=k){
p[i]=j;
k-=tmpsum[j-1];
del(j);
break;
}
}
}
REP(i, 1, n) printf("%lld ", p[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3808kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3860kb
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: 3552kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3796kb
input:
3 1
output:
1 2 3
result:
wrong answer 2nd numbers differ - expected: '3', found: '2'