QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#278108#6353. Kth Lex Min Min Min Subpalindromespaul2008#AC ✓53ms29280kbC++232.4kb2023-12-07 12:13:362023-12-07 12:13:36

Judging History

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

  • [2023-12-07 12:13:36]
  • 评测
  • 测评结果:AC
  • 用时:53ms
  • 内存:29280kb
  • [2023-12-07 12:13:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e6+5;
const int INF=1e18+1;

int ways[N],rk[N],ans[N],a[N];
int tmp[15]={0,11,13,19,22,25,26,37,38,41,44,50,52};

bool check(int l,int r)
{
	for(int i=l;i<=r;i++)
		if(a[i]!=a[r-i+l])
			return false;
	return true;
}

signed main()
{
	int n,m,k;
	cin >> n >> m >> k;
	if(n==1)
	{
		if(m>=k)
			printf("%lld\n",k);
		else
			printf("-1\n");
		return 0;
	}

	if(m==1)
	{
		if(k==1)
		{
			for(int i=1;i<=n;i++)
				printf("1 ");
			printf("\n");
		}
		else
			printf("-1\n");
		return 0;
	}

	if(m==2)
	{
		if(n<=6)
		{
			int ans=1000;
			for(int S=0;S<1<<n;S++)
			{
				for(int i=1;i<=n;i++)
					a[i]=(S>>(i-1))&1;

				int cnt=0;
				for(int i=1;i<=n;i++)
					for(int j=i;j<=n;j++)
						if(check(i,j))
							cnt++;
				ans=min(ans,cnt);
			}

			for(int S=0;S<1<<n;S++)
			{
				for(int i=1;i<=n;i++)
					a[i]=(S>>(n-i))&1;

				int cnt=0;
				for(int i=1;i<=n;i++)
					for(int j=i;j<=n;j++)
						if(check(i,j))
							cnt++;

				if(cnt==ans)
				{
					k--;
					if(k==0)
					{
						for(int i=1;i<=n;i++)
							printf("%d ",a[i]+1);
						return 0;
					}
				}
			}
			printf("-1\n");
			return 0;
		}

		if(k>12)
		{
			printf("-1\n");
			return 0;
		}

		int S=tmp[k];
		for(int i=1;i<=6;i++)
			a[i]=(S>>(6-i))&1;

		for(int i=7;i<=n;i++)
			a[i]=a[i-6];

		for(int i=1;i<=n;i++)
			printf("%d ",a[i]+1);
		return 0;
	}

	ways[n+1]=1;
	for(int i=n;i>=1;i--)
	{
		if(i==1)
		{
			if(ways[i+1]<=INF/m)
				ways[i]=ways[i+1]*m;
			else
				ways[i]=INF;
		}
		else if(i==2)
		{
			if(ways[i+1]<=INF/(m-1))
				ways[i]=ways[i+1]*(m-1);
			else
				ways[i]=INF;
		}
		else
		{
			if(ways[i+1]<=INF/(m-2))
				ways[i]=ways[i+1]*(m-2);
			else
				ways[i]=INF;
		}
	}

	if(k>ways[1])
	{
		printf("-1\n");
		return 0;
	}

	for(int i=1;i<=n;i++)
	{
		rk[i]=(k+ways[i+1]-1)/ways[i+1];
		k -= (rk[i]-1)*ways[i+1];
	}

	ans[0]=1e18;
	for(int i=1;i<=n;i++)
	{
		if(i==1)
			ans[i]=rk[i];
		else
		{
			if(rk[i]<ans[i-1] && rk[i]<ans[i-2])
				ans[i]=rk[i];
			else if(rk[i]+1<max(ans[i-1],ans[i-2]) && rk[i]+1>min(ans[i-1],ans[i-2]))
				ans[i]=rk[i]+1;
			else if(rk[i]+2>ans[i-1] && rk[i]+2>ans[i-2])
				ans[i]=rk[i]+2;
		}

		printf("%lld ",ans[i]);
	}
	return 0;
}

详细

Test #1:

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

input:

1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

2 2 2

output:

2 1 

result:

ok 2 number(s): "2 1"

Test #3:

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

input:

3 3 3

output:

2 1 3 

result:

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

Test #4:

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

input:

9 9 8244353

output:

2 4 1 2 6 8 1 2 7 

result:

ok 9 numbers

Test #5:

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

input:

10 7 998244353

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

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

input:

3 1000 994253860

output:

998 244 353 

result:

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

Test #7:

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

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: 0ms
memory: 5760kb

input:

58 4 864691128455135233

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 49ms
memory: 27932kb

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: 51ms
memory: 29280kb

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

input:

1 1 2

output:

-1

result:

ok 1 number(s): "-1"

Test #12:

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

input:

1 2 2

output:

2

result:

ok 1 number(s): "2"

Test #13:

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

input:

2 2 1

output:

1 2 

result:

ok 2 number(s): "1 2"

Test #14:

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

input:

3 2 4

output:

2 1 1 

result:

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

Test #15:

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

input:

3 2 7

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

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

input:

4 2 10

output:

2 2 1 2 

result:

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

Test #17:

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

input:

4 2 3

output:

1 2 1 1 

result:

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

Test #18:

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

input:

5 2 7

output:

2 1 1 2 1 

result:

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

Test #19:

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

input:

5 2 13

output:

-1

result:

ok 1 number(s): "-1"

Test #20:

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

input:

6 2 5

output:

1 2 2 1 1 2 

result:

ok 6 numbers

Test #21:

score: 0
Accepted
time: 33ms
memory: 13088kb

input:

1000000 2 3

output:

1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 ...

result:

ok 1000000 numbers

Test #22:

score: 0
Accepted
time: 38ms
memory: 13284kb

input:

1000000 2 5

output:

1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 ...

result:

ok 1000000 numbers

Test #23:

score: 0
Accepted
time: 41ms
memory: 13364kb

input:

1000000 2 7

output:

2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 ...

result:

ok 1000000 numbers

Test #24:

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

input:

1000000 2 1000000000000000000

output:

-1

result:

ok 1 number(s): "-1"

Test #25:

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

input:

1 3 2

output:

2

result:

ok 1 number(s): "2"

Test #26:

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

input:

2 3 5

output:

3 1 

result:

ok 2 number(s): "3 1"

Test #27:

score: 0
Accepted
time: 53ms
memory: 27912kb

input:

1000000 3 5

output:

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 1 2 ...

result:

ok 1000000 numbers

Test #28:

score: 0
Accepted
time: 2ms
memory: 13084kb

input:

1000000 3 7

output:

-1

result:

ok 1 number(s): "-1"

Test #29:

score: 0
Accepted
time: 49ms
memory: 27652kb

input:

1000000 4 211106232532991

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 #30:

score: 0
Accepted
time: 46ms
memory: 27948kb

input:

1000000 5 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 #31:

score: 0
Accepted
time: 42ms
memory: 27476kb

input:

1000000 123123 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 #32:

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

input:

6 1000000 1000000000000000000

output:

1 2 4 9 15 8 

result:

ok 6 numbers

Test #33:

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

input:

4 1000000 1000000000000000000

output:

2 7 15 9 

result:

ok 4 number(s): "2 7 15 9"

Test #34:

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

input:

3 1000000 999997000002000000

output:

1000000 999999 999998 

result:

ok 3 number(s): "1000000 999999 999998"

Test #35:

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

input:

3 1000000 999997000002000001

output:

-1

result:

ok 1 number(s): "-1"