QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#507277 | #6353. Kth Lex Min Min Min Subpalindromes | ucup-team052# | WA | 1ms | 5932kb | C++23 | 4.2kb | 2024-08-06 15:09:51 | 2024-08-06 15:09:51 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
using LL=long long;
const __int128 INF=1000000000000000005;
const LL inf=1000000000000000005;
#define N 1000005
#define int long long
int mul(int x,int y){return min((__int128)x*y,INF);}
int add(int x,int y){return min(x+y,inf);}
int a[N],pw[N],n,m,k;
const int L=5,ful=(1<<L)-1;
int f[N][1<<5],v[20],ok[1<<5],ok2[1<<5][2];
signed main(){
#ifdef xay5421
// cout<<sizeof(f)/1024.0/1024<<endl;
int n=9,mn=inf,ccnt=0;
for(int st=0;st<1<<n;st++)
{
for(int i=0;i<n;i++) v[i]=st>>i&1;
int cnt=0;
for(int i=0;i<n;i++) for(int j=i;j<n;j++)
{
int len=j-i+1;
int ok=1;
for(int l=0;l<len;l++) ok&=v[i+l]==v[j-l];
cnt+=ok;
}
if(cnt==2*n-2)
{
// for(int i=0;i<n;i++) printf("%d%c",v[n-i-1]+1," \n"[i==n-1]);
}
}
// cout<<mn<<" "<<ccnt<<endl;
freopen("b.in","r",stdin);
#endif
cin>>n>>m>>k;
if(m==1)
{
if(k>1) printf("-1\n");
else
{
for(int i=1;i<=n;i++) printf("1%c"," \n"[i==n]);
}
}
else if(n==1)
{
if(k>m) printf("-1\n");
else printf("%lld\n",k);
}
else if(m==2)
{
/*
for(int st=0;st<1<<L;st++)
{
ok[st]=1;
for(int j=0;j+2<L;j++) if((st>>j&7)==0||(st>>j&7)==7) ok[st]=0;
for(int j=0;j<L;j++) v[j]=st>>j&1;
for(int j=0;j<L;j++) ok[st]&=v[j]==v[L-j-1];
}
for(int st=0;st<1<<L;st++) for(int c=0;c<2;c++)
{
ok2[st][c]=1;
int tst=st<<1|c;
for(int j=0;j+2<=L;j++) if((tst>>j&7)==0||(tst>>j&7)==7) ok2[st][c]=0;
for(int j=0;j<=L;j++) v[j]=tst>>j&1;
for(int j=0;j<=L;j++) ok2[st][c]&=v[j]==v[L-j-1];
}
*/
f[n+1][0]=1;
for(int i=n;i>=1;i--) for(int st=0;st<1<<L;st++) if(f[i+1][st])
{
for(int j=0;j<L;j++) v[j+1]=st>>j&1;
for(int c=0;c<2;c++)
{
v[0]=c;
if(i+2<=n)
{
if(v[0]==v[1]&&v[1]==v[2]) continue;
}
if(i+4<=n)
{
int ok=1;
for(int j=0;j<L;j++) ok&=v[j]==v[L-j-1];
if(ok) continue;
}
if(i+5<=n)
{
int ok=1;
for(int j=0;j<=L;j++) ok&=v[j]==v[L-j];
if(ok) continue;
}
int nst=(st<<1|c)&ful;
f[i][nst]=add(f[i][nst],f[i+1][st]);
}
}
int sum=0;
for(int j=0;j<1<<L;j++) sum=add(sum,f[1][j]);
// printf("%lld\n",sum);
if(sum<k) printf("-1\n");
else
{
int lst=0;
for(int i=1;i<=n;i++)
{
for(int c=0;c<2;c++)
{
int all=0;
for(int st=0;st<1<<L;st++)
{
if((st&1)!=c) continue;
int cv=0;
for(int j=0;j<min(L,i-1);j++) v[cv++]=lst>>j&1;
reverse(v,v+cv);
for(int j=0;j<L&&i+j<=n;j++) v[cv++]=st>>j&1;
int ok=1;
for(int i=0;i+2<cv;i++)
{
if(v[i]==v[i+1]&&v[i+1]==v[i+2]) ok=0;
}
for(int i=0;i+4<cv;i++)
{
if(v[i]==v[i+4]&&v[i+1]==v[i+3]) ok=0;
}
for(int i=0;i+5<cv;i++)
{
if(v[i]==v[i+5]&&v[i+1]==v[i+4]&&v[i+2]==v[i+3]) ok=0;
}
if(!ok) continue;
// printf("* %d %d\n",i,st);
all=add(all,f[i][st]);
}
if(all<k) k-=all;
else
{
lst=(lst<<1|c)&ful;
printf("%lld%c",c+1," \n"[i==n]);
break;
}
}
}
}
}
else
{
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=mul(pw[i-1],m-2);
pw[n-1]=mul(pw[n-2],m-1);
pw[n]=mul(pw[n-1],m);
if(pw[n]<k) printf("-1\n");
else
{
int l0=-1,l1=-1;
for(int i=n;i>=1;i--)
{
for(int j=1;j<=m;j++)
{
if(j==l0||j==l1) continue;
if(k>pw[i-1]) k-=pw[i-1];
else
{
printf("%lld%c",j," \n"[i==1]);
l1=l0,l0=j;
break;
}
}
}
}
}
return 0;
}
/*
1 1 2 1 2 2 1 1 2
1 1 2 2 1 2 1 1 2
1 2 1 1 2 2 1 2 1
1 2 1 2 2 1 1 2 1
1 2 2 1 1 2 1 2 2
1 2 2 1 2 1 1 2 2
2 1 1 2 1 2 2 1 1
2 1 1 2 2 1 2 1 1
2 1 2 1 1 2 2 1 2
2 1 2 2 1 1 2 1 2
2 2 1 1 2 1 2 2 1
2 2 1 2 1 1 2 2 1
* 1 22
* 1 26
1 * 2 11
* 2 13
2 * 3 6
1 * 4 19
2 * 5 9
2 * 6 4
* 6 20
1 * 7 2
* 7 10
* 7 18
* 7 26
1 * 8 1
* 8 5
* 8 9
* 8 13
* 8 17
* 8 21
* 8 25
* 8 29
2 * 9 0
* 9 2
* 9 4
* 9 6
* 9 8
* 9 10
* 9 12
* 9 14
* 9 16
* 9 18
* 9 20
* 9 22
* 9 24
* 9 26
* 9 28
* 9 30
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5728kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5932kb
input:
2 2 2
output:
1 2
result:
wrong answer 1st numbers differ - expected: '2', found: '1'