QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#149660#6353. Kth Lex Min Min Min Subpalindromesqzez#WA 2ms5756kbC++142.1kb2023-08-25 08:19:342023-08-25 08:19:36

Judging History

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

  • [2023-08-25 08:19:36]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5756kb
  • [2023-08-25 08:19:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
int calc(vector<int>a){
	int n=a.size(),ans=0;
	for(int i=0,j;i<n;i++){
		for(j=0;i-j>=0&&i+j<n&&a[i-j]==a[i+j];j++);
		ans+=j;
	}
	for(int i=0,j;i+1<n;i++){
		for(j=0;i-j>=0&&i+j+1<n&&a[i-j]==a[i+1+j];j++);
		ans+=j;
	}
	return ans;
}
vector<int> gen(int S,int n){
	vector<int>a;
	for(int i=n-1;i>=0;i--)a.push_back(S>>i&1);
	return a;
}
const int N=1e6+10;
int n,m,k;
void solve(){
	int n=min(::n,6),U=(1<<n)-1,mn=n*n;
	for(int S=0;S<=U;S++)mn=min(mn,calc(gen(S,n)));
	for(int S=0;S<=U;S++){
		auto a=gen(S,n);
		if(calc(a)==mn&&!--k){
			for(int i=0;i<n;i++)printf("%d%c",a[i%6]+1,"\n "[i+1<n]);
			exit(0);
		}
	}
	puts("-1");
}
using big=__int128;
ll pw[N];
ll mul(ll x,ll y){
	return min((big)x*y,(big)k);
}
int calc(int i){
	if(i==1)return mul(m-1,pw[n-2]);
	return pw[n-i];
}
int ans[N];
int main(){
	cin>>n>>m>>k;
	if(m==1){
		if(k>1)return cout<<-1<<endl,0;
		for(int i=1;i<=n;i++)printf("1 ");
		return cout<<endl,0;
	}
	if(m==2){
		return solve(),0;
	}
	if(n==1){
		if(k>m)return cout<<-1<<endl,0;
		return cout<<k<<endl,0;
	}
	for(int i=pw[0]=1;i<=n;i++)pw[i]=mul(pw[i-1],m-2);
	if(mul(m,mul(m-1,pw[n-2]))<k)return cout<<-1<<endl,0;
	k--;
	for(int i=1;i<=n;i++){
		ll base=calc(i);
		int cur=k/base+1;
		k%=base;
		if(i==1)printf("%d ",ans[i]=cur);
		else if(i==2){
			if(cur<ans[1])printf("%d ",ans[i]=cur);
			else printf("%d ",ans[i]=cur+1);
		}else{
			int x=ans[i-1],y=ans[i-2];
			if(x>y)swap(x,y);
			if(cur<x)printf("%d ",ans[i]=cur);
			else if(cur<y-1)printf("%d ",ans[i]=cur+1);
			else printf("%d ",ans[i]=cur+2);
		}
	}
	cout<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3524kb

input:

1 1 1

output:

1 

result:

ok 1 number(s): "1"

Test #2:

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

input:

2 2 2

output:

2 1

result:

ok 2 number(s): "2 1"

Test #3:

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

input:

3 3 3

output:

2 1 3 

result:

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

Test #4:

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

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

input:

10 7 998244353

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

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

input:

3 1000 994253860

output:

998 244 353 

result:

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

Test #7:

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

input:

58 4 864691128455135232

output:

2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 

result:

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