@[Diaоsi](/user/137242)
建议去 loj 或者 uoj
by zimujun @ 2021-02-24 08:18:49
@[zimujunqwq](/user/118196) UOJ跟LOJ都试过了，目前只有Acwing上的数据过不了。
by Diaоsi @ 2021-02-24 08:20:17
@[Diaоsi](/user/137242) 看不了你代码，您开了不公开？
by zimujun @ 2021-02-24 08:21:05
@[zimujunqwq](/user/118196) https://www.luogu.com.cn/paste/yc51aqqd
by Diaоsi @ 2021-02-24 08:22:14
@[Diaоsi](/user/137242) ~~可能卡常卡的太优秀了~~
by zimujun @ 2021-02-24 08:23:25
@[zimujunqwq](/user/118196) 问题是根本没有刻意地去卡啊，你看看我代码，我感觉是数据强度的问题，有些题目 $3\times 10^5$ 就可以把这个做法卡掉了，更何况这是 $10^6$
by Diaоsi @ 2021-02-24 08:24:58
@[Diaоsi](/user/137242)
加了一句之后它甚至吊打了我的基排
```cpp
#include<bits/stdc++.h>
typedef long long LL;
typedef long double LD;
using namespace std;
const int N=1000010,INF=0x3f3f3f3f;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
int n,w,sa[N],rk[N<<1],oldrk[N<<1];
char s[N];
int main(){
int i,p;
scanf("%s",s+1);
n=strlen(s+1);
for(i=1;i<=n;i++)
sa[i]=i,rk[i]=s[i];
for(w=1;w<n;w<<=1){
sort(sa+1,sa+n+1,[](int x,int y){
return rk[x]==rk[y]?rk[x+w]<rk[y+w]:rk[x]<rk[y];
});
memcpy(oldrk,rk,sizeof(rk));
for(i=1,p=0;i<=n;i++)
if(oldrk[sa[i]]==oldrk[sa[i-1]]&&
oldrk[sa[i]+w]==oldrk[sa[i-1]+w])
rk[sa[i]]=p;
else rk[sa[i]]=++p;
if(p == n) break;//Here is it
}
for(i=1;i<=n;i++)
printf("%d ",sa[i]);
return 0;
}
```
by zimujun @ 2021-02-24 08:29:03
@[zimujunqwq](/user/118196) 草，这个快的飞起
by Diaоsi @ 2021-02-24 08:30:44
我也是$O(nlog^2n)$过的QwQ。
by zjrdmd @ 2021-02-24 08:39:44
这卡不掉吧，我最慢的不到1s,[记录](https://www.luogu.com.cn/record/46595435)
by zjrdmd @ 2021-02-24 08:42:09