提交记录 16207
提交时间 |
评测时间 |
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;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 8.061 ms | 46 MB + 272 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 8.268 ms | 46 MB + 276 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #3 | 7.959 ms | 46 MB + 276 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 7.966 ms | 46 MB + 280 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 8.201 ms | 46 MB + 280 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 8.152 ms | 46 MB + 280 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 55.852 ms | 54 MB + 848 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 73.81 ms | 55 MB + 608 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 61.596 ms | 55 MB + 868 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 41.07 ms | 52 MB + 348 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 42.671 ms | 52 MB + 380 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 85.058 ms | 59 MB + 8 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 81.704 ms | 59 MB + 100 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #14 | 64.065 ms | 55 MB + 752 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #15 | 66.802 ms | 56 MB + 308 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #16 | 81.903 ms | 58 MB + 956 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #17 | 81.467 ms | 59 MB + 36 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #18 | 78.17 ms | 58 MB + 844 KB | Wrong Answer | Score: 0 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 20:02:30 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用