QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#703393#7778. Turning PermutationPandaGhostWA 1ms3860kbC++175.0kb2024-11-02 17:42:322024-11-02 17:42:33

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 17:42:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3860kb
  • [2024-11-02 17:42:32]
  • 提交

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'