记录编号	167829	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2005.[USACO Dec07]最佳老农(金组)	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.304 s
提交时间	2015-06-29 09:11:22	内存使用	2.03 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=60010;
void basesort(int a[],int b[],int c[],int n,int m){//排序前a,排序后b,关键字c,下标0~n-1,关键字0~m
	static int sum[SIZEN]={0};
	memset(sum,0,sizeof(sum));
	for(int i=0;i<n;i++) sum[c[a[i]]]++;
	for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
	for(int i=n-1;i>=0;i--) b[--sum[c[a[i]]]]=a[i];
}
void sort_suf(char S[],int rank[],int sa[],int N){//串S,名次数组rank,顺序数组sa,下标0~N-1
	static int A[SIZEN],B[SIZEN];
	static int x[SIZEN],y[SIZEN];
	for(int i=0;i<N;i++) x[i]=S[i],A[i]=i;
	basesort(A,sa,x,N,256);
	rank[sa[0]]=1;
	for(int i=1;i<N;i++){
		if(x[sa[i]]==x[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
		else rank[sa[i]]=rank[sa[i-1]]+1;
	}
	for(int k=1;k<=N;k<<=1){
		for(int i=0;i<N;i++){
			x[i]=rank[i];
			y[i]=i+k<N?rank[i+k]:0;
			A[i]=i;
		}
		basesort(A,B,y,N,N);
		basesort(B,sa,x,N,N);
		rank[sa[0]]=1;
		for(int i=1;i<N;i++){
			if(x[sa[i]]==x[sa[i-1]]&&y[sa[i]]==y[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
			else rank[sa[i]]=rank[sa[i-1]]+1;
		}
	}
	for(int i=0;i<N;i++) rank[sa[i]]=i;
}
int N;
char S[SIZEN];
int rank[SIZEN],sa[SIZEN];
char ans[SIZEN];
void work(void){
	sort_suf(S,rank,sa,2*N+1);
	int l=0,r=N-1;
	int tot=0;
	while(l<r){
		if(rank[l]<=rank[2*N-r]){
			ans[tot++]=S[l];
			l++;
		}
		else{
			ans[tot++]=S[r];
			r--;
		}
	}
	ans[tot++]=S[l];
	int p=0;
	for(int i=0;i<N;i++){
		printf("%c",ans[i]);
		p++;
		if(p==80){
			printf("\n");
			p=0;
		}
	}
}
void read(void){
	scanf("%d\n",&N);
	for(int i=0;i<N;i++){
		S[i]=getchar();
		getchar();
	}
	S[N]='#';
	for(int i=0;i<N;i++) S[N+1+i]=S[N-1-i];
}
int main(){
	freopen("bclgold.in","r",stdin);
	freopen("bclgold.out","w",stdout);
	read();
	work();
	return 0;
}