TLE了,求大佬帮忙给孩子看看病吧
查看原帖
TLE了,求大佬帮忙给孩子看看病吧
132976
huayucaiji楼主2020/8/22 22:22

rt,几乎都是600ms,开了O2都过不了/kk

//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
//#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
//#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}

const int maxn=11e6+10;

int n,p[maxn],tot;
char s[maxn<<1];
char ch;

void manacher() {
	int mx=1,mid=1;
	n=tot;
	for(int i=1;i<=n;i++) {
		if(i<mx) {
			p[i]=p[mid*2-i];
		}
		else {
			p[i]=1;
		}
		while(s[i+p[i]]==s[i-p[i]]) {
			p[i]++;
		}
		if(mx<i+p[i]) {
			mid=i;
			mx=i+p[i];
		}
	}
}

signed main() {
	//freopen("temp.in","r",stdin);
	//freopen(".out","w",stdout);
	while(scanf("%c",&ch)!=EOF) {
		s[++tot]='#';
		s[++tot]=ch;
	}
	s[++tot]='#';
	
	manacher();
	
	int ans=p[1];
	for(int i=2;i<=n;i++) {
		ans=max(p[i],ans);
	}
	
	cout<<ans-1<<endl; 

	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

2020/8/22 22:22
加载中...