PKU 3581: Sequence

ｻの練習。蟻本みて書いた。勉強しないといけないですね。
PKUにはこの手の問題が大量にある。

#include<stdio.h>
#include<algorithm>
using namespace std;
int b[410000];
int c[410000];
int z[410000];
int n;
int k;
int rank[410000];
int tmp[410000];
int sa[410000];
bool compare_sa(int i,int j){
	if(rank[i]!=rank[j])return rank[i]<rank[j];
	else{
		int ri=i+k<=n?rank[i+k]:-1;
		int rj=j+k<=n?rank[j+k]:-1;
		return ri<rj;
	}
}
void construct_sa(){
	for(int i=0;i<=n;i++){
		sa[i]=i;
		rank[i]=i<n?c[i]:-1;
	}
	for(k=1;k<=n;k*=2){
		sort(sa,sa+n+1,compare_sa);
		tmp[sa[0]]=0;
		for(int i=1;i<=n;i++){
			tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
		}
		for(int i=0;i<=n;i++){
			rank[i]=tmp[i];
		}
	}
}
int ret[210000];
int main(){
	int a;
	scanf("%d",&a);
	n=a;
	for(int i=0;i<a;i++)scanf("%d",b+i);
	for(int i=0;i<a;i++)z[i]=b[i];
	std::sort(z,z+a);
	for(int i=0;i<a;i++)b[i]=lower_bound(z,z+a,b[i])-z;
	for(int i=0;i<a;i++){
		c[i]=b[a-1-i];
	}
	construct_sa();
	int sz=0;
//	printf("%d\n",sa[1]);
	int st=0;
	for(int i=0;i<=n;i++){
		if(sa[i]<n&&sa[i]>1){
			st=sa[i];
			break;
		}
	}
	for(int i=st;i<a;i++){
		ret[sz++]=c[i];
	}
	n-=sz;
	for(int i=0;i<n;i++){
		c[n+i]=c[i];
	}
	n*=2;
//	for(int i=0;i<n;i++)printf("%d\n",z[c[i]]);
	construct_sa();
	int gd=0;
//	for(int i=0;i<=n;i++)printf("%d ",sa[i]);
	for(int i=0;i<=n;i++){
		if(sa[i]&&sa[i]<n/2){
			gd=sa[i];break;
		}
	}
	//printf("%d\n",gd);
	for(int i=0;i<n/2;i++)ret[sz++]=c[gd+i];
	for(int i=0;i<a;i++){
		printf("%d\n",z[ret[i]]);
	}
}
/*
4: ""
2: 34
0: 3434
3: 4
1: 434
*/