记录编号	414197	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Dec07]最佳老农(金组)	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	0.043 s
提交时间	2017-06-13 17:54:05	内存使用	2.16 MiB

#include <stdio.h>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 200100;
char ch[MAXN];
int N,m,len,sa[MAXN],t1[MAXN],t2[MAXN],c[MAXN],rank[MAXN];


void get_sa(){
    int i,p,k,*x=t1,*y=t2;
    for(i=0;i<m;++i) c[i]=0;
    for(i=0;i<N;++i) c[x[i]=ch[i]]++;
    for(i=1;i<m;++i) c[i]+=c[i-1];
    for(i=N-1;i>=0;--i) sa[--c[x[i]]]=i;
    for(k=1;k<=N;k<<=1){
        p=0;
        for(i=N-k;i<N;++i) y[p++]=i;
        for(i=0;i<N;++i) if(sa[i]>=k) y[p++]=sa[i]-k;
        for(i=0;i<m;++i) c[i]=0;
        for(i=0;i<N;++i) c[x[y[i]]]++;
        for(i=0;i<m;++i) c[i]+=c[i-1];
        for(i=N-1;i>=0;--i) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;x[sa[0]]=0;
        for(i=1;i<N;++i)
         x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
        if(p>=N) break;
        m=p;
    }
}

inline void read(char &a){while(a=getchar(),a>'Z'||a<'A');}

int zz(){
    freopen("bclgold.in","r",stdin);
    freopen("bclgold.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)read(ch[i]);
    for(int i=0;i<n;i++)ch[i]-='A'-1;
    ch[n]=0;
    ch[2*n+1]=0;
    N=2*n+2;
    m=28;
    for(int i=1;i<=n;i++)ch[n+i]=ch[n-i];
    get_sa();
    for(int i=1;i<N;i++)rank[sa[i]]=i;
    int A=0,B=n+1;
    while(A+B-n-1<n){
        if (rank[A] < rank[B])       putchar(ch[A++] + 'A' - 1);  
        else putchar( ch[B++] + 'A' - 1);          
        if (!((A + B - n - 1)%80))  putchar('\n');  
    }
}

int zzh=zz();

int main(){;}