Submission #3789

#	Time	Username	Problem	Language	Result	Execution time	Memory
3789		mjy0503	Make superpalindrome! (kriii1_M)	C++98	0 / 1	16 ms	5012 KiB

M

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
int n,pa[100001],height[100001];
char mun[100001],maxc[100001];
bool check[100001];
using namespace std;
vector<int> list[100001];
int parent(int a){
	if(pa[a]==-1)
		return a;
	return parent(pa[a]);
}
void back(int s,int e){
	if(s+1==e)
		return ;
	if((e-s)%2==0){
		back(s,(s+e)/2);
		back((s+e)/2,e);
	}
	else{
		back(s,(s+e)/2);
		back((s+e)/2+1,e);
	}
	e--;
	int pa1,pa2;
	while(s<=e){
		pa1=parent(s);
		pa2=parent(e);
		if(pa1!=pa2){
			if(height[pa1]==height[pa2])
				height[pa1]++;
			if(height[pa1]>height[pa2]){
				pa[pa2]=pa1;
				if(maxc[pa2]>maxc[pa1])
					maxc[pa1]=maxc[pa2];
			}
			else if(height[pa2]<height[pa1]){
				pa[pa1]=pa2;
				if(maxc[pa1]>maxc[pa2])
					maxc[pa2]=maxc[pa1];
			}
		}
		s++;
		e--;
	}
}
int main(){
	scanf("%s",mun);
	int i,j;
	n=strlen(mun);
	for(i=0;i<n;i++){
		pa[i]=-1;
		maxc[i]=mun[i];
	}
	back(0,n);
	int par;
	for(i=0;i<n;i++){
		par=parent(i);
		list[par].push_back(i);
	}
	for(i=0;i<n;i++){
		par=parent(i);
		if(check[par]) continue;
		check[par]=1;
		if(mun[i]==maxc[par]){
			for(j=0;j<list[par].size();j++)
				mun[list[par][j]]=maxc[par];
		}
		else{
			maxc[par]=mun[i]+1;
			for(j=0;j<list[par].size();j++)
				mun[list[par][j]]=maxc[par];
			for(j=i;j<n;j++){
				par=parent(j);
				if(check[par]) continue;
				mun[j]='a';
			}
			break;
		}
	}
	printf("%s\n",mun);
	return 0;
}

• Subtask 1: 0 / 1