QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203226#6353. Kth Lex Min Min Min SubpalindromesqzzyqWA 43ms12520kbC++142.2kb2023-10-06 16:12:562023-10-06 16:12:56

Judging History

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

  • [2023-10-06 16:12:56]
  • 评测
  • 测评结果:WA
  • 用时:43ms
  • 内存:12520kb
  • [2023-10-06 16:12:56]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,k;
int ans[maxn],pw[maxn];
void print(int id,int res) {
	int i;
	gdb(id,res,ans[id-1]);
	for (i=id;i<=n;i++) {
		gdb(i,res,pw[i]);
		int nums=(res+pw[i]-1)/pw[i],t=nums;
		if (i>=2&&t>=min(ans[i-1],ans[i-2])) t++;
		if (i>=3&&t>=max(ans[i-1],ans[i-2])) t++;
		ans[i]=t;
		res=res-(nums-1)*pw[i];
	}
	for (i=1;i<=n;i++) printf("%lld ",ans[i]);
	exit(0);
}
signed main(void){
	int i;
	read(n);read(m);read(k);
	if (m==1) {
		if (k>1) puts("-1");
		else {
			for (i=1;i<=n;i++) printf("%d ",1);
		}
		return 0;
 	}
 	if (m==2) {
 		if (k>2) puts("-1");
 		else if (k==1){
 			for (i=1;i<=n;i++) 
			 	if (i&1) printf("1 ");
 				else printf("2 ");
		}
		else {
			for (i=1;i<=n;i++) 
			 	if (i&1) printf("2 ");
 				else printf("1 ");
		} 
		return 0;
	}
	int res=1;
	ans[0]=1e9;
	for (i=1;i<=n;i++) ans[i]=(i-1)%3+1;
	for (i=n;i>=1;i--) {
		int tmp=m-2+(i<=2)+(i<=1);
		pw[i]=res;
		if ((long double)tmp*res>=k) {
			int nums=(k+res-1)/res,t=nums;
			gdb(i,nums);
			if (i>=2&&t>=min(ans[i-1],ans[i-2])) t++;
			if (i>=3&&t>=max(ans[i-1],ans[i-2])) t++;
			ans[i]=t;
			print(i+1,k-(nums-1)*res);
		}
		else res=res*tmp;
	}
	puts("-1");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1 1

output:

1 

result:

ok 1 number(s): "1"

Test #2:

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

input:

2 2 2

output:

2 1 

result:

ok 2 number(s): "2 1"

Test #3:

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

input:

3 3 3

output:

2 1 3 

result:

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

Test #4:

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

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

input:

10 7 998244353

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

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

input:

3 1000 994253860

output:

998 244 353 

result:

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

Test #7:

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

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

input:

58 4 864691128455135233

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 43ms
memory: 11860kb

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: 35ms
memory: 12520kb

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

input:

1 1 2

output:

-1

result:

ok 1 number(s): "-1"

Test #12:

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

input:

1 2 2

output:

2 

result:

ok 1 number(s): "2"

Test #13:

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

input:

2 2 1

output:

1 2 

result:

ok 2 number(s): "1 2"

Test #14:

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

input:

3 2 4

output:

-1

result:

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