oj.uz

답안 #3800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3800 2013-08-31T08:25:34 Z Apple_Cplus Make superpalindrome! (kriii1_M) C++
1 / 1
 8 ms 2552 KB 
#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

# 결과 실행 시간 메모리 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