记录编号	83511	评测结果	AAAAAAAAAAAAAA
题目名称	隐藏口令	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.046 s
提交时间	2013-12-03 20:45:11	内存使用	24.65 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<queue>
using namespace std;
typedef long long ll;
const int SIZEN=110000;
const int SIZEIND=18;
int n;
int ndig;//n在二进制下位数
int text[SIZEN]={0};//下标从0开始
ll eqnum[SIZEN][SIZEIND]={0};//[i][j]表示以i为起点,2^j位的等效整数
int jumpdes[SIZEN][SIZEIND]={0};//以i为起点,跳2^j步到达位置
void printtext(int x){//调试接口,从第x位开始输出文本
	for(int i=0;i<n;i++){
		cout<<text[x]<<" ";
		x++;x%=n;
	}
	cout<<endl;
}
class COUPLE{
public:
	int pos;
	ll data;
};
bool operator < (COUPLE a,COUPLE b){
	if(a.data<b.data) return true;
	if(a.data>b.data) return false;
	return a.pos<b.pos;
}
COUPLE s[SIZEN];
void work(void){
	ndig=(int)ceil(log((double)n)/log(2.0));
	int i,j;
	for(i=0;i<n-1;i++) jumpdes[i][0]=i+1;jumpdes[n-1][0]=0;
	for(i=0;i<n;i++) s[i].pos=i,s[i].data=text[i];
	sort(s,s+n);
	int tot=0;
	for(i=0;i<n;i++) eqnum[s[i].pos][0]=(i>0&&s[i].data!=s[i-1].data)?++tot:tot;
	for(j=1;j<=ndig;j++){
		for(i=0;i<n;i++) jumpdes[i][j]=jumpdes[jumpdes[i][j-1]][j-1];
		for(i=0;i<n;i++){
			s[i].pos=i,s[i].data=eqnum[i][j-1]*n+eqnum[jumpdes[i][j-1]][j-1];
		}
		sort(s,s+n);
		tot=0;
		for(i=0;i<n;i++) eqnum[s[i].pos][j]=(i>0&&s[i].data!=s[i-1].data)?++tot:tot;
	}
	//此时s中储存的是长度为2^ndig的比较信息
	printf("%d\n",s[0].pos);
}
void read(void){
	scanf("%d",&n);
	char ch;
	int i=-1;
	while(!cin.eof()){
		cin>>ch;
		if('a'<=ch&&ch<='z') text[++i]=ch-'a';
	}
}
int main(){
	freopen("hidden.in","r",stdin);
	freopen("hidden.out","w",stdout);
	read();
	work();
	return 0;
}