QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199393#6353. Kth Lex Min Min Min Subpalindromesucup-team870#WA 215ms16696kbC++142.8kb2023-10-04 11:15:182023-10-04 11:15:18

Judging History

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

  • [2023-10-04 11:15:18]
  • 评测
  • 测评结果:WA
  • 用时:215ms
  • 内存:16696kb
  • [2023-10-04 11:15:18]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define ilr int i,int l,int r
#define ls i<<1,l,mid
#define rs i<<1|1,mid+1,r
#define mi int mid=l+r>>1;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
string res[13];
const int N=1e6+6;
int num[N<<2];
void bu(ilr){
    num[i]=r-l+1;
    if(l==r)return;
    mi
    bu(ls); bu(rs);
}
void ud(ilr,int x,int v){
    num[i]+=v;
    if(l==r)return;
    mi
    if(mid>=x)ud(ls,x,v);
    else ud(rs,x,v);
}
int qu(ilr,int k){
    if(l==r)return l;
    mi
    if(num[i<<1]<k)return qu(rs,k-num[i<<1]);
    return qu(ls,k);
}
int main() {
    IOS
    int n,m; ll k;
    cin>>n>>m>>k;
    if(m==1){
        if(k>1){
end:        cout<<-1; return 0;
        }
        rep(i,1,n)cout<<1<<' ';
        return 0;
    }
    if(m==2){
        int tot=0;
        if(0){
end1:   
            if(k>tot)goto end;     
            for(auto v:res[k])cout<<v<<' ';
            return 0;
        }
        if(n==2){
            tot=2; res[1]="12"; res[2]="21"; goto end1;
        }
        if(n==3){
            tot=6; res[1]="112"; res[2]="121"; res[3]="122";
            res[4]="211"; res[5]="212"; res[6]="221";
            goto end1;
        }
        if(n==4){
            tot=10; res[1]="1121"; res[2]="1122"; res[3]="1211"; res[4]="1212"; res[5]="1221";
            res[6]="2112"; res[7]="2121"; res[8]="2122"; res[9]="2211"; res[10]="2212";
            goto end1;
        }
        string s1="121122",s2="212211";
        rep(i,0,5){
            int x=i; ++tot;
            rep(j,1,n)res[tot]+=s1[x],x=(x+1)%6;
        }
        rep(i,0,5){
            int x=i; ++tot;
            rep(j,1,n)res[tot]+=s2[x],x=(x+1)%6;
        }
        sort(res+1,res+tot+1);
        goto end1;
    }
    __int128 all=1;
    rep(i,1,n){
        if(i==1)all*=m;
        else if(i==2)all*=m-1;
        else all*=m-2;
        if(all>=k)break;
    }
    if(all<k)goto end;
    vector<int> ans(n+1);
    auto cal=[&](int x,ll k){
        __int128 res=1;
        if(m==3){
            return (ll)((x==2)?2:1);
        }
        rep(i,x,n){
            if(i==2)res*=m-1;
            else res*=m-2;
            if(res>k)return k+1;
        }
        return (ll)res;
    };
    bu(1,1,m);
    rep(i,1,n){
        ll rea=cal(i+1,k);
        int v=(k-1)/rea+1; k-=(v-1)*rea;
        //!=前2个的第v大
        rep(j,1,2){
            if(i-j<=0)break;
            ud(1,1,m,ans[i-j],-1);
        }
        ans[i]=qu(1,1,m,v);
        // cout<<v<<' ';
        rep(j,1,2){
            if(i-j<=0)break;
            ud(1,1,m,ans[i-j],1);
        }
    }
    rep(i,1,n)cout<<ans[i]<<' ';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3872kb

input:

1 1 1

output:

1 

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

2 2 2

output:

2 1 

result:

ok 2 number(s): "2 1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

3 3 3

output:

2 1 3 

result:

ok 3 number(s): "2 1 3"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

9 9 8244353

output:

2 4 1 2 6 8 1 2 7 

result:

ok 9 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

10 7 998244353

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

3 1000 994253860

output:

998 244 353 

result:

ok 3 number(s): "998 244 353"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

58 4 864691128455135232

output:

4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 

result:

ok 58 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

58 4 864691128455135233

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 131ms
memory: 16696kb

input:

1000000 1000000 1000000000000000000

output:

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...

result:

ok 1000000 numbers

Test #10:

score: 0
Accepted
time: 215ms
memory: 7108kb

input:

1000000 4 1000000000000000000

output:

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...

result:

ok 1000000 numbers

Test #11:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

1 1 2

output:

-1

result:

ok 1 number(s): "-1"

Test #12:

score: -100
Wrong Answer
time: 0ms
memory: 3516kb

input:

1 2 2

output:

1 

result:

wrong answer 1st numbers differ - expected: '2', found: '1'