Submission #3697

#	Time	Username	Problem	Language	Result	Execution time	Memory
3697		pichulia	Make superpalindrome! (kriii1_M)	C++98	1 / 1	0 ms	1184 KiB

M

#include<stdio.h>
#include<string.h>

int n;
char a[100005];

bool checksuper(int st,int en){
	int i;
	if(st==en)
		return true;
	for(i=st;i<=en;i++)
		if(a[i]!=a[en-i+st])
			return false;
	if((en-st+1)%2==0)
		return checksuper(st,(en+st)/2)&&checksuper((en+st)/2+1,en);
	return checksuper(st,(en+st-1)/2)&&checksuper((en+st-1)/2+2,en);
}

void makesuper(int st,int en){
	int i;
	bool ch=true;
	if(checksuper(st,en))
		return;
	if(checksuper(st,(st+en-1)/2)){
		if((en-st+1)%2==0){
			for(i=(st+en)/2+1;i<=en;i++){
				if(a[i]<a[en-i+st]){
					ch=true;
					break;
				}
				else if(a[i]>a[en-i+st]){
					ch=false;
					break;
				}
			}
			if(ch){
				for(i=(st+en)/2+1;i<=en;i++)
					a[i]=a[en-i+st];
			}
			else{
				for(i=(st+en)/2;i>=st;--i)
					if(a[i]!='z'){
						a[i]++;
						break;
					}
				makesuper(st,(st+en)/2);
				for(i=(st+en)/2+1;i<=en;i++)
					a[i]=a[en-i+st];
			}
		}
		else{
			for(i=(st+en-1)/2+2;i<=en;i++){
				if(a[i]<a[en-i+st]){
					ch=true;
					break;
				}
				else if(a[i]>a[en-i+st]){
					ch=false;
					break;
				}
			}
			if(ch){
				for(i=(st+en-1)/2+2;i<=en;i++)
					a[i]=a[en-i+st];
			}
			else{
				if(a[(st+en-1)/2+1]!='z')
					a[(st+en-1)/2+1]++;
				else{
					for(i=(st+en-1)/2;i>=st;--i)
						if(a[i]!='z'){
							a[i]++;
							break;
						}
					makesuper(st,(st+en-1)/2);
					a[(st+en-1)/2+1]='a';
				}
				for(i=(st+en-1)/2+2;i<=en;i++)
					a[i]=a[en-i+st];
			}
		}
	}
	else{
		if((en-st+1)%2==0){
			makesuper(st,(st+en)/2);
			for(i=en;i>=(st+en)/2+1;--i)
				a[i]=a[en-i+st];
		}
		else{
			makesuper(st,(st+en-1)/2);
			for(i=en;i>=(st+en-1)/2+2;--i)
				a[i]=a[en-i+st];
			a[(st+en-1)/2+1]='a';
		}
	}
}

int main(){
	scanf("%s",&a[1]);
	n=strlen(&a[1]);
	makesuper(1,n);
	printf("%s",&a[1]);
	return 0;
}

• Subtask 1: 1 / 1