QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548309#6353. Kth Lex Min Min Min SubpalindromesMoyunAllgorithm#WA 41ms8748kbC++142.9kb2024-09-05 17:03:242024-09-05 17:03:27

Judging History

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

  • [2024-09-05 17:03:27]
  • 评测
  • 测评结果:WA
  • 用时:41ms
  • 内存:8748kb
  • [2024-09-05 17:03:24]
  • 提交

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);
	/*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;
	}
	a[0]=100000000;
	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(i!=1)
			{
				t+=1ll*min(a[i-1],a[i-2])<=t;
				t+=1ll*max(a[i-1],a[i-2])<=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!=1)
		{
			t+=1ll*min(a[i-1],a[i-2])<=t;
			t+=1ll*max(a[i-1],a[i-2])<=t;
		}
		a[i]=t;
	}
	if(N!=1)
	{
		K+=1ll*min(a[N-1],a[N-2])<=K;
		K+=1ll*max(a[N-1],a[N-2])<=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: 3892kb

input:

1 1 1

output:

1 

result:

ok 1 number(s): "1"

Test #2:

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

input:

2 2 2

output:

2 1

result:

ok 2 number(s): "2 1"

Test #3:

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

input:

3 3 3

output:

2 1 3 

result:

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

Test #4:

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

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: 5780kb

input:

10 7 998244353

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

score: 0
Accepted
time: 1ms
memory: 5964kb

input:

3 1000 994253860

output:

998 244 353 

result:

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

Test #7:

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

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: 1ms
memory: 5820kb

input:

58 4 864691128455135233

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 40ms
memory: 8248kb

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: 41ms
memory: 8748kb

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: 3724kb

input:

1 1 2

output:

-1

result:

ok 1 number(s): "-1"

Test #12:

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

input:

1 2 2

output:

-1

result:

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