提交记录 16207


用户 题目 状态 得分 用时 内存 语言 代码长度
zhoufangyuanPT 1006. 【模板题】后缀排序 Wrong Answer 0 85.058 ms 60516 KB C++ 840 B
提交时间 评测时间
2021-04-26 21:13:29 2021-04-26 21:13:34
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
char s[1010000];
int rk[2][1010000];
vector<int> sa[2][1010000];
int f,ff,i;
inline bool cmp(int x,int y){return rk[f][x+i]<rk[f][y+i];}
int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	if(n==1)
	{
		puts("1");
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		rk[0][i]=s[i];
		sa[0][s[i]].push_back(i);
	}
	int m=127;
	for(i=1,f=0,ff=1;i<n;i<<=1,f^=1,ff^=1)
	{
		int ms=0;
		for(int j=1;j<=m;j++)
		{
			sort(sa[f][j].begin(),sa[f][j].end(),cmp);
			for(int k=0;k<sa[f][j].size();k++)
			{
				if(k==0||rk[f][sa[f][j][k-1]+i]<rk[f][sa[f][j][k]+i])ms++;
				rk[ff][sa[f][j][k]]=ms;
				sa[ff][ms].push_back(sa[f][j][k]);
			}
			sa[f][j].clear();
		}
		m=ms;
	}
	for(int i=1;i<n;i++)printf("%d ",sa[f][i][0]);
	printf("%d\n",sa[f][n][0]);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #18.061 ms46 MB + 272 KBWrong AnswerScore: 0

Subtask #1 Testcase #28.268 ms46 MB + 276 KBWrong AnswerScore: 0

Subtask #1 Testcase #37.959 ms46 MB + 276 KBWrong AnswerScore: 0

Subtask #1 Testcase #47.966 ms46 MB + 280 KBWrong AnswerScore: 0

Subtask #1 Testcase #58.201 ms46 MB + 280 KBWrong AnswerScore: 0

Subtask #1 Testcase #68.152 ms46 MB + 280 KBWrong AnswerScore: 0

Subtask #1 Testcase #755.852 ms54 MB + 848 KBWrong AnswerScore: 0

Subtask #1 Testcase #873.81 ms55 MB + 608 KBWrong AnswerScore: 0

Subtask #1 Testcase #961.596 ms55 MB + 868 KBWrong AnswerScore: 0

Subtask #1 Testcase #1041.07 ms52 MB + 348 KBWrong AnswerScore: 0

Subtask #1 Testcase #1142.671 ms52 MB + 380 KBWrong AnswerScore: 0

Subtask #1 Testcase #1285.058 ms59 MB + 8 KBWrong AnswerScore: 0

Subtask #1 Testcase #1381.704 ms59 MB + 100 KBWrong AnswerScore: 0

Subtask #1 Testcase #1464.065 ms55 MB + 752 KBWrong AnswerScore: 0

Subtask #1 Testcase #1566.802 ms56 MB + 308 KBWrong AnswerScore: 0

Subtask #1 Testcase #1681.903 ms58 MB + 956 KBWrong AnswerScore: 0

Subtask #1 Testcase #1781.467 ms59 MB + 36 KBWrong AnswerScore: 0

Subtask #1 Testcase #1878.17 ms58 MB + 844 KBWrong AnswerScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 20:02:30 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用