답안 #3554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
3554	2013-08-31T06:33:51 Z	zzapcoder	Make superpalindrome! (kriii1_M)	C++	0 / 1	4 ms	2256 KB

M

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;
string next_1(string a){
	int carry = 1;
	for(int i=a.size()-1;i>=0;--i)
		if(carry)
			if(a[i] == 'z') a[i] = 'a';
			else{ 
				a[i] += 1;
				carry = 0;
			}
		else break;
	return a;
}
string makeSuper(string s){
	string L, R;
	int sz = s.size(), sz2 = s.size()/2;

	if(sz == 1) return s;
	if(sz == 2){
		for(int i=0;i<26;++i){
			if(s <= string(2, 'a'+i)) return string(2,'a'+i);
		}
	}

	L = s.substr(0, sz2);
	if(sz&1) R = s.substr(sz2+1, sz2);
	else R = s.substr(sz2, sz2);
	string sL, sR;
	sL = makeSuper(L);

	if(sz&1){
		char m = s[sz2];
		if(sL != L) return sL + "a" + sL;
		if(m < 'z'){
			string ret(sL);
			ret += m+1;
			ret += sL;
			return ret;
		}
		if(sL >= R){
			string ret(sL);
			ret += m;
			ret += sL;
			return ret;
		}
		//이와중에 sL == L 이라서 R도 못 바꾸고, R보다 작고 m도 z이고 해서 노답인 경우
		return makeSuper(next_1(sL) + "a" + string(sz2, 'a'));
	}
	//문자열이 짝수인 경우 입니다.
	if(sL != L) return sL + sL;
	//L이 슈퍼팰린드롬인 경우
	if(sL >= R) return sL + sL;
	//L이 슈퍼팰린드롬인데 R보다 작아서 R을 L로 만들수 없음
	return makeSuper(next_1(sL) + string(sz2, 'a'));
}

int main(){
	string s;
	cin >> s;
	cout<<makeSuper(s)<<endl;
}

Subtask #1

0.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2248 KB	Output is correct
2	Correct	4 ms	2220 KB	Output is correct
3	Correct	4 ms	2072 KB	Output is correct
4	Correct	0 ms	2256 KB	Output is correct
5	Correct	4 ms	2248 KB	Output is correct
6	Incorrect	0 ms	1676 KB	Output isn't correct
7	Halted	0 ms	0 KB	-