답안 #3697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3697 2013-08-31T07:43:27 Z pichulia Make superpalindrome! (kriii1_M) C++
1 / 1
0 ms 1184 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1184 KB Output is correct
2 Correct 0 ms 1184 KB Output is correct
3 Correct 0 ms 1184 KB Output is correct
4 Correct 0 ms 1184 KB Output is correct
5 Correct 0 ms 1184 KB Output is correct
6 Correct 0 ms 1184 KB Output is correct
7 Correct 0 ms 1184 KB Output is correct
8 Correct 0 ms 1184 KB Output is correct
9 Correct 0 ms 1184 KB Output is correct
10 Correct 0 ms 1184 KB Output is correct
11 Correct 0 ms 1184 KB Output is correct
12 Correct 0 ms 1184 KB Output is correct
13 Correct 0 ms 1184 KB Output is correct
14 Correct 0 ms 1184 KB Output is correct
15 Correct 0 ms 1184 KB Output is correct
16 Correct 0 ms 1184 KB Output is correct
17 Correct 0 ms 1184 KB Output is correct
18 Correct 0 ms 1184 KB Output is correct
19 Correct 0 ms 1184 KB Output is correct
20 Correct 0 ms 1184 KB Output is correct