QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#425021#6353. Kth Lex Min Min Min Subpalindromesushg8877WA 1ms11428kbC++141.5kb2024-05-29 21:23:222024-05-29 21:23:23

Judging History

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

  • [2024-05-29 21:23:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:11428kb
  • [2024-05-29 21:23:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
const int MAXN=1e6+5;
ll n,m,k;
LL pw(LL a,int b){LL r=1;while(b){if(b&1)r=min(r*a,(LL)k+1);a=min(a*a,(LL)k+1),b>>=1;}return min(r,(LL)k+1);}
int ans[MAXN],b[MAXN];
bool check(int x){
	if(x>=3&&b[x-2]==b[x-1]&&b[x-1]==b[x]) return false;
	if(x>=5&&b[x-3]==b[x-1]&&b[x-4]==b[x]) return false;
	if(x>=6&&b[x-5]==b[x]&&b[x-4]==b[x-1]&&b[x-3]==b[x-2]) return false;
	return true;
}
void dfs(int u){
	if(!k) return;
	if(u==n+1){
		if(--k==0) swap(ans,b);
		return;
	}
	for(int o:{1,2}){
		b[u]=o;
		if(check(u)){
			dfs(u+1);
			if(!k) return;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	// freopen("Otomachi_Una.in","r",stdin);
	// freopen("Otomachi_una.out","w",stdout);
	cin>>n>>m>>k;
	if(n==1){
		if(k<=m) cout<<k;
		else cout<<"-1";
		return 0;
	}
	if(m==1){
		if(k==1){
			for(int i=1;i<=n;i++) cout<<"1 ";
		}else cout<<"-1";
	}else if(m>=3){
		for(int x=1;x<=m;x++){
			if(k>(m-1)*pw(m-2,n-2)) k-=(m-1)*pw(m-2,n-2);
			else{
				ans[1]=x;
				break;
			}
		}
		if(!ans[1]) cout<<"-1";
		else{
			for(int i=2;i<=n;i++){
				for(int j=1;j<=m;j++)if(j!=ans[i-1]&&j!=ans[i-2]){
					if(k>pw(m-2,n-i)) k-=pw(m-2,n-i);
					else{
						ans[i]=j;
						break;
					}
				}
			}
			for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
		}
	}else{
		// hard one :(, I think that has no 111 and 000 and any 5/6- palind in it?
		dfs(1);
		if(k) cout<<"-1";
		else{
			for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

2 2 2

output:

1 2 

result:

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