提交记录 20380
提交时间 |
评测时间 |
2023-10-13 21:22:41 |
2023-10-13 21:22:49 |
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
using ull=unsigned long long;
char ch[N];
int n,rk[N],sa[N],ht[N];
ull hsh[N],pw[N],p=131;
bool cmp(int a,int b){
int fl=0;
if(a>b)swap(a,b),fl=1;
int l=0,r=n-b-1,ans=-1;
while(r>=l){
int mid=(l+r)>>1;
if((hsh[a+mid]-hsh[a-1])*pw[b-a]==hsh[b+mid]-hsh[b-1])ans=mid,l=mid+1;
else r=mid-1;
}
if(b+ans==n-1)return fl;
return fl^(ch[a+ans+1]<ch[b+ans+1]);
}
int main(){
cin>>ch;
n=strlen(ch);
pw[0]=1;
for(int i=1;i<n;i++)pw[i]=pw[i-1]*p;
for(int i=0;i<n;i++)hsh[i]=(ch[i]-28)*pw[i]+hsh[i-1];
for(int i=0;i<n;i++)sa[i]=i;
stable_sort(sa,sa+n,cmp);
for(int i=0;i<n;i++)rk[sa[i]]=i,printf("%d ",sa[i]+1);
puts("");
for(int i=0,k=0;i<n;i++){
if(rk[i]==0)continue;
k-=!!k;
while(ch[i+k]==ch[sa[rk[i]-1]+k])k++;
ht[rk[i]]=k;
}
for(int i=1;i<n;i++)printf("%d ",ht[i]);
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 36.83 us | 56 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 37.37 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #3 | 36.75 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 41.81 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 41.51 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 42.61 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 85.322 ms | 3 MB + 784 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 99.876 ms | 3 MB + 972 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 95.77 ms | 3 MB + 836 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 59.768 ms | 2 MB + 524 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 62.649 ms | 2 MB + 564 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 52.62 ms | 4 MB + 140 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 71.861 ms | 4 MB + 108 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #14 | 97.219 ms | 3 MB + 864 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #15 | 105.011 ms | 3 MB + 880 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #16 | 61.463 ms | 4 MB + 140 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #17 | 67.946 ms | 4 MB + 140 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #18 | 68.404 ms | 4 MB + 140 KB | Accepted | Score: 0 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2025-08-02 15:11:42 | Loaded in 2 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠