Submission #3800

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3800	2013-08-31T08:25:34 Z	Apple_Cplus	Make superpalindrome! (kriii1_M)	C++	1 / 1	8 ms	2552 KB

M

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
 
using namespace std;
 
#define ll long long
#define pi pair<int,int>
#define pll pair<ll,ll>
#define pii pair<int,pi>
#define X first
#define Y second
#define pb push_back
#define ab(x) ((x)<0?(-(x)):(x))
#define xx(x) ((x)*(x))
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
#define vpi vector<pi>
#define vpll vector<pll>
#define ALL(x) (x).begin(),(x).end()
#define Max (1<<30)
#define LLMax (1ll<<60)
template<class T>string ToString(T t){stringstream s;s<<t;return s.str();}
template<class T>void ToOther(T&t,string a){stringstream s(a);s>>t;}
 
 



char a[100005];
int n;
string A;


void UP(string &A){
	int n=A.size();
	
	int s,e;
	s=n/2;e=n/2;
	if(A.size()%2==0)e++;
	
	A[s]++;
	

	for(s;s>=0;s--,e++){
		if(A[s]>'z'){
			A[s]='a';
			A[e]='a';

			A[s-1]++;
			A[e+1]++;
		}else break;
	}

}

int P[100005];
bool ck[100005];
int F(int x){
	if(P[x]!=x)P[x]=F(P[x]);
	return P[x];
}

void mer(int s,int e){
	if(s>=e)return;

	int L=(e-s+1);
	int M=L/2;
	int S=s,E=e;

	while(S<=E){
		P[F(E)]=F(S);
		S++;E--;
	}

	if(L%2){
		mer(s,s+M-1);
		mer(s+M+1,e);
	}
	else{
		mer(s,s+M-1);
		mer(s+M,e);
	}
}
vi v;
string now;
char st[100005];

bool go(int x,int same){
	if(x==A.size())return 1;

	int k=F(P[x]);

	if(st[k]){
		if(same && st[k]<A[x])return 0;

		now[x]=st[k];
		int nxt=0;
		if(same && st[k]==A[x])nxt=1;
		if(go(x+1,nxt))return 1;

	}else{
		char ss=A[x];
		if(same==0)ss='a';
		for(ss;ss<=A[x]+2;ss++){
			int nxt=0;
			st[k]=ss;
			if(same && ss==A[x])nxt=1;
			now[x]=ss;
			if(go(x+1,nxt))return 1;
		}
	}
	return 0;
}
int main(){
	scanf("%s",&a);
	A=a;
	n=A.size();
	now=A;

	for(int i=0;i<n;i++)P[i]=i;


	mer(0,n-1);

	
	for(int i=0;i<n;i++){
		int t=F( P[i] );
		if(ck[t])continue;
		ck[t]=1;
		v.pb(t);
	}

	go(0,1);

	cout<<now<<endl;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	2544 KB	Output is correct
2	Correct	8 ms	2548 KB	Output is correct
3	Correct	8 ms	2536 KB	Output is correct
4	Correct	8 ms	2552 KB	Output is correct
5	Correct	8 ms	2548 KB	Output is correct
6	Correct	0 ms	2356 KB	Output is correct
7	Correct	0 ms	2356 KB	Output is correct
8	Correct	0 ms	2356 KB	Output is correct
9	Correct	0 ms	2356 KB	Output is correct
10	Correct	8 ms	2540 KB	Output is correct
11	Correct	8 ms	2544 KB	Output is correct
12	Correct	8 ms	2548 KB	Output is correct
13	Correct	8 ms	2552 KB	Output is correct
14	Correct	8 ms	2544 KB	Output is correct
15	Correct	4 ms	2536 KB	Output is correct
16	Correct	4 ms	2488 KB	Output is correct
17	Correct	8 ms	2488 KB	Output is correct
18	Correct	0 ms	2488 KB	Output is correct
19	Correct	8 ms	2540 KB	Output is correct
20	Correct	4 ms	2488 KB	Output is correct