Submission #21996

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
21996	2017-04-28T15:22:10 Z	gs14004	Make superpalindrome! (kriii1_M)	C++11	1 / 1	6 ms	3048 KB

M

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

string rv(string s){
	reverse(s.begin(), s.end());
	return s;
}

bool is_super(string s){
	if(s.size() <= 1) return 1;
	string w = s.substr(0, s.size() / 2);
	return is_super(w) && (w + s.substr(s.size() / 2, s.size() % 2) + rv(w)) == s;
}

string solve(string s){
	if(s.size() == 1){
		s[0]++;
		return s;
	}
	string t = s.substr(0, s.size() / 2);
	string ans = t + s.substr(s.size() / 2, s.size() % 2) + rv(t);
	if(is_super(t) && ans > s) return ans;
	if(is_super(t) && s.size() % 2 == 1 && s[s.size()/2] < 'z'){
		ans[s.size()/2]++;
		return ans;
	}
	t = solve(t);
	if(s.size() % 2 == 0) return t + rv(t);
	else return t + "a" + rv(t);
}

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

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3048 KB	Output is correct
2	Correct	3 ms	2964 KB	Output is correct
3	Correct	3 ms	2632 KB	Output is correct
4	Correct	3 ms	2988 KB	Output is correct
5	Correct	0 ms	3036 KB	Output is correct
6	Correct	0 ms	2024 KB	Output is correct
7	Correct	0 ms	2156 KB	Output is correct
8	Correct	0 ms	2156 KB	Output is correct
9	Correct	0 ms	2024 KB	Output is correct
10	Correct	3 ms	2608 KB	Output is correct
11	Correct	3 ms	2616 KB	Output is correct
12	Correct	3 ms	2768 KB	Output is correct
13	Correct	6 ms	2720 KB	Output is correct
14	Correct	6 ms	2764 KB	Output is correct
15	Correct	6 ms	2740 KB	Output is correct
16	Correct	3 ms	2736 KB	Output is correct
17	Correct	3 ms	2736 KB	Output is correct
18	Correct	0 ms	2612 KB	Output is correct
19	Correct	3 ms	2836 KB	Output is correct
20	Correct	3 ms	2660 KB	Output is correct