QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#548423#6353. Kth Lex Min Min Min SubpalindromesMoyunAllgorithm#RE 0ms0kbC++143.0kb2024-09-05 18:11:292024-09-05 18:11:30

Judging History

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

  • [2024-09-05 18:11:30]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-09-05 18:11:29]
  • 提交

answer

#include <bits/stdc++.h>
#define LL long long
#define int 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("%lld %lld %lld %lld %lld %lld ",c[1],c[2],c[3],c[4],c[5],c[6]);
	}
	for(int i=1;i<=N;i++) printf("%lld ",c[i]);
	puts("");
	exit(0);
}
LL cnt[MAXN];
int a[MAXN];
signed main()
{
	//freopen("moyun.in","r",stdin);
	freopen("moyun.out","w",stdout);
	scanf("%lld %lld %lld",&N,&M,&K);
	if(M<3)
	{
		for(int i=1;i;i=i) N++;
		return 0;
	}
	if(M==1) Func1();
	if(M==2) Func2();
	if(N==1)
	{
		if(K>M) puts("-1");
		else printf("%lld\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;
			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;
			break;
		}
		cnt[i]=cnt[i+1]*nxt;
	}
//	printf("%lld\n",K);
	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("%lld ",a[i]);
	puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

1 1 1

output:


result: