记录编号	371233	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Dec07]最佳老农(金组)	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.140 s
提交时间	2017-02-15 19:04:28	内存使用	5.63 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005<<1;
int r[maxn],N;
int sa[maxn],wa[maxn],wb[maxn],cnt[maxn],Rank[maxn],height[maxn];
inline bool R_cmp(int *y,int a,int b,int len){
	return y[a]==y[b]&&y[a+len]==y[b+len];
}
void Rabit_sa(int n,int m){
	int *t,*x=wa,*y=wb,i,j,p;
	for(i=0;i<m;i++)cnt[i]=0;
	for(i=0;i<n;i++)cnt[x[i]=r[i]]++;
	for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
	for(i=n-1;~i;i--)sa[--cnt[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p){
		for(p=0,i=n-j;i<n;i++)y[p++]=i;
		for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
		for(i=0;i<m;i++)cnt[i]=0;
		for(i=0;i<n;i++)cnt[x[y[i]]]++;
		for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
		for(i=n-1;~i;i--)sa[--cnt[x[y[i]]]]=y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
			x[sa[i]]=R_cmp(y,sa[i],sa[i-1],j)?p-1:p++;
	}
}
void Rabit_H(int n){
	int i,j,k=0;
	for(i=0;i<=n;i++)Rank[sa[i]]=i;
	for(i=0;i<n;height[Rank[i++]]=k)
	for(k?k--:k,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
}
void Rabit_ans(){
	int s=0,t=(N>>1)-1;
	while(s<t)
		if(Rank[s]<Rank[N-t-1])putchar(r[s++]);
		else putchar(r[t--]);
	putchar(r[s]);
}
int main(){
	freopen("bclgold.in","r",stdin);freopen("bclgold.out","w",stdout);
	scanf("%d",&N);int i;char s[5];
	for(i=0;i<N;i++)scanf("%s",s),r[i]=s[0];r[N]=1;
	for(i=1;i<=N;i++)r[N+i]=r[N-i];
	r[N=N<<1|1]=0;Rabit_sa(N+1,200),Rabit_H(N);
	Rabit_ans();
}