QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548335#6353. Kth Lex Min Min Min SubpalindromesMoyunAllgorithm#TL 0ms3852kbC++143.1kb2024-09-05 17:16:262024-09-05 17:16:26

Judging History

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

  • [2024-09-05 17:16:26]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3852kb
  • [2024-09-05 17:16:26]
  • 提交

answer

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=1e6+5;
int N,M;
LL K;
void Func1()
{
	if(K!=1)
	{
		puts("-1");
		exit(0);
	}
	for(int i=1;i<=N;i++) printf("1 ");
	exit(0);
}
int tab[13]={0,112122,112212,121122,121221,122112,122121,211212,211221,212112,212211,221121,221211};
void Func2()
{
	int kkk=2*N-2;
	if(K>kkk)
	{
		puts("-1");
		exit(0);
	}
	if(N==1)
	{
		printf("%d\n",K);
		exit(0);
	}
	if(N==2)
	{
		if(K==1) puts("1 2");
		if(K==2) puts("2 1");
		exit(0);
	}
	if(N==3)
	{
		if(K==1) puts("1 1 2");
		if(K==2) puts("1 2 1");
		if(K==3) puts("1 2 2");
		if(K==4) puts("2 1 1");
		if(K==5) puts("2 1 2");
		if(K==6) puts("2 2 1");
		exit(0);
	}
	if(N==4)
	{
		if(K==1) puts("1 1 2 1");
		if(K==2) puts("1 1 2 2");
		if(K==3) puts("1 2 1 1");
		if(K==4) puts("1 2 1 2");
		if(K==5) puts("1 2 2 1");
		if(K==6) puts("2 1 1 2");
		if(K==7) puts("2 1 2 1");
		if(K==8) puts("2 1 2 2");
		if(K==9) puts("2 2 1 1");
		if(K==10) puts("2 2 1 2");
		exit(0);
	}
	if(N==5)
	{
		if(K==1) puts("1 1 2 1 2");
		if(K==2) puts("1 1 2 2 1");
		if(K==3) puts("1 2 1 1 2");
		if(K==4) puts("1 2 1 2 2");
		if(K==5) puts("1 2 2 1 1");
		if(K==6) puts("1 2 2 1 2");
		if(K==7) puts("2 1 1 2 1");
		if(K==8) puts("2 1 1 2 2");
		if(K==9) puts("2 1 2 1 1");
		if(K==10) puts("2 1 2 2 1");
		if(K==11) puts("2 2 1 1 2");
		if(K==12) puts("2 2 1 2 1");
		exit(0);
	}
	int term=N/6;
	N-=term*6;
	int c[10];
	for(int i=6;i;i--)
	{
		c[i]=tab[K]%10;
		tab[K]/=10;
	}
	for(int i=1;i<=term;i++)
	{
		printf("%d %d %d %d %d %d ",c[1],c[2],c[3],c[4],c[5],c[6]);
	}
	for(int i=1;i<=N;i++) printf("%d ",c[i]);
	puts("");
	exit(0);
}
LL cnt[MAXN];
int a[MAXN];
int main()
{
	scanf("%d %d %lld",&N,&M,&K);
//	for(int i=1;i<=1;i=i) N++;
	//	return 0;
	/*if(N>6&&M==2)
	{
		for(int i=1;i<=1;i=i) N++;
		return 0;
	}*/
	if(M==1) Func1();
	if(M==2) Func2();
	if(N==1)
	{
		if(K>M) puts("-1");
		else printf("%d\n",K);
		return 0;
	}
	a[0]=3;
	for(int i=1;i<=N;i++)
	{
		if(a[i-1]==3) a[i]=1;
		else a[i]=a[i-1]+1;
	}
	cnt[N]=M-2;
	if(N==2) cnt[N]++;
	int S=0;
	for(int i=N-1;i;i--)
	{
		int nxt=M-2+(i<=2)+(i<=1);
		__int128 ncnt=(__int128)cnt[i+1]*nxt;
		if(ncnt>(__int128)K)
		{
			S=i;
			//pri
			LL t=(K+cnt[i+1]-1)/cnt[i+1];
			K-=cnt[i+1]*(t-1);
			if((__int128)cnt[i+1]*(t-1)>K)
			{
				for(int i=1;i;i=i) N++;
			}
			if(i>2)
			{
				t+=1ll*min(a[i-1],a[i-2])<=t;
				t+=1ll*max(a[i-1],a[i-2])<=t;
			}
			if(i==2) t+=1ll*a[i-1]<=t;
			a[i]=t;
			break;
		}
		cnt[i]=cnt[i+1]*nxt;
		//printf("%d %lld\n",i,cnt[i]);
	}
	if(S==0&&cnt[1]<K)
	{
		puts("-1");
		return 0;
	}
	for(int i=S+1;i<N;i++)
	{
		LL t=(K+cnt[i+1]-1)/cnt[i+1];
		K-=cnt[i+1]*(t-1);
		if(i>2)
		{
			t+=1ll*min(a[i-1],a[i-2])<=t;
			t+=1ll*max(a[i-1],a[i-2])<=t;
		}
		if(i==2) t+=1ll*a[i-1]<=t;
		a[i]=t;
	}
	if(N>2)
	{
		K+=1ll*min(a[N-1],a[N-2])<=K;
		K+=1ll*max(a[N-1],a[N-2])<=K;
	}
	if(N==2) K+=1ll*a[N-1]<=K;
	a[N]=K;
	for(int i=1;i<=N;i++) printf("%d ",a[i]);
	puts("");
	return 0;
}

详细

Test #1:

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

input:

1 1 1

output:

1 

result:

ok 1 number(s): "1"

Test #2:

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

input:

2 2 2

output:

2 1

result:

ok 2 number(s): "2 1"

Test #3:

score: -100
Time Limit Exceeded

input:

3 3 3

output:


result: