Submission #3666

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3666	2013-08-31T07:27:39 Z	zzapcoder	Make superpalindrome! (kriii1_M)	C++	1 / 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;
		//L == sL
		if(sL >= R){
			string ret(sL);
			ret += m;
			ret += sL;
			return ret;
		}
		// sl == L < R
		if(m < 'z'){
			string ret(sL);
			ret += m+1;
			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'));
}
string solve(string s){//s가 슈퍼팰린드롬인지 확인하고, 맞다면 +1 시켜주고 구합니다.
	string sps = makeSuper(s);
	if(sps == s){
		for(int i=0;i<s.size();++i){
			if(s[i] != 'z') break;
			if(i == s.size()-1) return s;
		}
		return makeSuper(next_1(s));
	}
	return sps;
}

int main(){
	string s;
	cin >> s;
	cout<<solve(s)<<endl;
	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	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	4 ms	2256 KB	Output is correct
5	Correct	4 ms	2248 KB	Output is correct
6	Correct	0 ms	1676 KB	Output is correct
7	Correct	0 ms	1676 KB	Output is correct
8	Correct	0 ms	1676 KB	Output is correct
9	Correct	0 ms	1676 KB	Output is correct
10	Correct	4 ms	2100 KB	Output is correct
11	Correct	0 ms	2144 KB	Output is correct
12	Correct	0 ms	2144 KB	Output is correct
13	Correct	4 ms	2056 KB	Output is correct
14	Correct	4 ms	2236 KB	Output is correct
15	Correct	4 ms	2132 KB	Output is correct
16	Correct	4 ms	2112 KB	Output is correct
17	Correct	4 ms	2112 KB	Output is correct
18	Correct	4 ms	2112 KB	Output is correct
19	Correct	0 ms	2100 KB	Output is correct
20	Correct	4 ms	2112 KB	Output is correct