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
#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;
}
# 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