QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#507277#6353. Kth Lex Min Min Min Subpalindromesucup-team052#WA 1ms5932kbC++234.2kb2024-08-06 15:09:512024-08-06 15:09:51

Judging History

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

  • [2024-08-06 15:09:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5932kb
  • [2024-08-06 15:09:51]
  • 提交

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'