QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199387#6353. Kth Lex Min Min Min Subpalindromesucup-team870#WA 1ms3476kbC++142.2kb2023-10-04 11:07:382023-10-04 11:07:39

Judging History

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

  • [2023-10-04 11:07:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3476kb
  • [2023-10-04 11:07:38]
  • 提交

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){
        string s1="121122",s2="212211";
        int tot=0;
        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);
        if(k>12)goto end;
        for(auto v:res[k])cout<<v<<' ';
        return 0;
    }
    __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: 1ms
memory: 3476kb

input:

1 1 1

output:

1 

result:

ok 1 number(s): "1"

Test #2:

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

input:

2 2 2

output:

1 1 

result:

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