QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378933 | #8571. Palworld | ucup-team052# | AC ✓ | 792ms | 47284kb | C++23 | 2.7kb | 2024-04-06 15:18:09 | 2024-04-06 15:18:19 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=400005,K=20;
int lg[N];
struct SA{
char s[N];
int n,m;
int sa[N],rk[N],tmp[N],h[N],bin[N],f[N][K];
void radixSort(){
rep(i,0,m)bin[i]=0;
rep(i,1,n)++bin[rk[i]];
rep(i,1,m)bin[i]+=bin[i-1];
per(i,n,1)sa[bin[rk[tmp[i]]]--]=tmp[i];
}
void getSa(){
rep(i,1,n)rk[i]=s[i],tmp[i]=i;
radixSort();
for(int l=1,p=0;p<n;m=p,l<<=1){
p=0;
rep(i,n-l+1,n)tmp[++p]=i;
rep(i,1,n)if(sa[i]>l)tmp[++p]=sa[i]-l;
radixSort();
rep(i,1,n)swap(rk[i],tmp[i]);
rk[sa[1]]=p=1;
rep(i,2,n){
int k1=sa[i-1]+l<=n?tmp[sa[i-1]+l]:0;
int k2=sa[i ]+l<=n?tmp[sa[i ]+l]:0;
rk[sa[i]]=(tmp[sa[i-1]]==tmp[sa[i]]&&k1==k2?p:++p);
}
}
}
void getHeight(){
int k=0;
rep(i,1,n){
if(k)--k;
int j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
h[rk[i]]=k;
}
rep(i,1,n)f[i][0]=h[i];
rep(j,1,K-1)rep(i,1,n-(1<<j)+1)f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
void init(char *t){
n=strlen(t+1);
rep(i,1,n)s[i]=t[i];
m=256;
getSa();
getHeight();
}
int ask(int l,int r){
int x=lg[r-l+1];
return min(f[l][x],f[r-(1<<x)+1][x]);
}
int LCP(int k1,int k2){
if(k1<0||k2<0||k1>n||k2>n)return 0;
k1=rk[k1],k2=rk[k2];
if(k1>k2)swap(k1,k2);
if(k1==k2)return n-sa[k1]+1;
else return ask(k1+1,k2);
}
}A;
int T,n,k;
char s[N],s0[N];
int h[N];
int query(int a,int b){
if(a<1||b>n)return 0;
return min({a,n+1-b,A.LCP(n*2+1-a,b)});
}
signed main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
rep(i,2,N-1)lg[i]=lg[i>>1]+1;
cin>>T;
while(T--){
scanf("%d%d",&n,&k);
scanf("%s",s+1);
rep(i,1,n){
s[n+i]=s[n+1-i];
}
s[n+n+1]=0;
A.init(s);
rep(i,1,n)s0[i]=s[i];
s[0]='#';
int m=0;
rep(i,1,n){
s[++m]='$';
s[++m]=s0[i];
}
s[++m]='$';
s[m+1]='!';
int ans=k+min(n,k+1);
int max_r=0,pos=0;
rep(i,1,m){
if(max_r>i){
h[i]=min(max_r-i,h[pos*2-i]);
}else{
h[i]=1;
}
while(s[i-h[i]]==s[i+h[i]])++h[i];
if(i+h[i]>max_r){
max_r=i+h[i];
pos=i;
}
ans=max(ans,h[i]-1);
if(i&1){
ans=max(ans,h[i]-1+k);
}
}
rep(i,1,m){
int l=(i-h[i])/2+1;
int r=(i+h[i])/2-1;
rep(_,1,k){
if(r+_<=n){
ans=max(ans,h[i]-1+query(l-1,r+_+1)*2+_*2);
}
if(l-_>=1){
ans=max(ans,h[i]-1+query(l-_-1,r+1)*2+_*2);
}
}
}
printf("%d\n",ans);
}
return 0;
}
/*
(gdb) p *h@20
$1 = {0, 1, 2, 1, 2, 1, 4, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
(gdb) p *s@20
$2 = "#$i$c$p$c$!\000\000\000\000\000\000\000\000
*/
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15664kb
input:
4 1 3 a 4 1 icpc 4 2 icpc 8 4 icecream
output:
4 5 5 11
result:
ok 4 number(s): "4 5 5 11"
Test #2:
score: 0
Accepted
time: 552ms
memory: 47256kb
input:
1 200000 66 jsmwjmibgkjvdscqllsxpaxiycmpauhnzschbivtqbjfrxrqvhvfbqecozjewqqpwdfbeqppjkgxhbnniopkptkygspcdswhwadfwhnzovvpshgcdukrupeztkpxwhmctaquqbxtidzbbxsyuaeikuldaoeudletrsmqptaejibkymsjhmwykqsjdvvdaqwelrcpxwrwhuvodipjniowfofbjktkdezwqqbvwsppsmpilntmdmlxgkaxymnugmmcsljkjzjuudnllydwdwwanadynsoiolso...
output:
141
result:
ok 1 number(s): "141"
Test #3:
score: 0
Accepted
time: 759ms
memory: 47276kb
input:
1 200000 100 qhiaajzxinenucrnfffumuhnovpuwcnojbhsktztapgyivmfqrlntwazwnfetwqieckxcnkskpidltiydfoveaucckximydxxfbiwbdufmbhywqkflyqxbijakadqkzftlciccbpnldsqhtjxuxnvkusvizavuyfhdroiuominebadhfqzrpjnzpgyvkejfwmueiltyeqpvwrkanqknyacqganbszktocfuvvsfrboaennwpaabfdnaurvvurysrijnfaonesihbhrrvbvyhpbremsuhhbc...
output:
209
result:
ok 1 number(s): "209"
Test #4:
score: 0
Accepted
time: 55ms
memory: 15636kb
input:
10000 21 7 fhcjhdjcfbfbdeeheibhg 18 8 hccgjfaadefhjhcijc 15 7 ahefiiheaigjiid 15 3 fgjjebidbfgbdij 15 5 jccebbgjbhifjhb 20 2 hcbddhibgfccjjcfebcc 19 1 ehbdgiicchijebidbcd 20 8 gbcfghefhbjggecdhcbj 17 2 jjaeaccjbcfiehfdd 23 4 iafjedfbebbhcfgfjbehdaf 22 1 jgiiiaacehcbaiehfggcfi 17 2 jefbbfigfhbhfcici ...
output:
17 21 17 11 13 9 6 18 9 11 6 9 22 8 21 23 5 23 7 16 9 23 25 11 17 12 9 5 20 5 23 12 7 13 16 17 21 21 21 12 16 21 21 8 9 11 21 15 5 24 13 7 21 13 11 8 7 19 25 7 8 12 13 22 15 14 7 15 7 20 15 13 11 15 5 11 23 17 17 19 15 7 19 17 25 13 23 10 17 21 9 21 7 23 21 13 16 7 14 10 13 10 9 11 7 21 15 19 11 23 ...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 142ms
memory: 47284kb
input:
1 200000 100 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
200100
result:
ok 1 number(s): "200100"
Test #6:
score: 0
Accepted
time: 661ms
memory: 47084kb
input:
1 200000 73 jgqahsycxmrrwvszqigkxmxxckratkgiyyqbxgjzaqkufvkgmepixhjdugpsntlsgtiedueukiytrytrcvlkymwibsfdhytbffmtaytnfczbavrrbdnpegwxubyeoopzopqhrwukohojtaizsureefffglwjfawvpqqnjteveuscyelgjiukskvymqejzwlnrjgvnpwnttzahoupruedryqeyahxgltnibxhbpxmhxxnmrebsgbjwsfpipezkekaqptnwtuanbfyfwyotwkrvlamnuvhunty...
output:
175682
result:
ok 1 number(s): "175682"
Test #7:
score: 0
Accepted
time: 26ms
memory: 15732kb
input:
10000 12 1 jelwdrimpvtq 19 8 qcogumialfqhaahfhtb 11 12 tbnfsiqbibv 5 4 hdehb 4 1 ivxi 7 8 nonrwqa 14 16 obvpfqjekvmnyq 4 5 fzhi 18 17 gploorpjnrrhcrgxlp 2 3 pf 7 9 uiliuyr 1 3 v 3 3 bgj 9 4 tektrwtmk 10 4 vvkvbzpbye 20 5 jqzqpqiwkssksbilayvj 2 4 kl 5 2 vptsk 20 9 kuiwsxhfmirnrhzuysqd 8 8 aairrgjl 15...
output:
3 20 23 9 5 15 30 9 35 5 16 4 6 11 11 14 6 5 21 16 13 11 2 23 13 3 30 5 23 15 21 16 18 21 3 3 11 23 13 13 8 14 4 22 6 5 13 3 18 27 9 3 24 32 28 3 13 3 31 18 3 7 8 3 15 20 7 13 19 15 3 7 3 15 12 4 7 29 5 3 11 36 23 5 26 22 11 8 12 30 7 9 25 11 3 3 9 12 15 22 10 2 17 15 21 7 31 33 7 35 18 31 11 10 10 ...
result:
ok 10000 numbers
Test #8:
score: 0
Accepted
time: 39ms
memory: 15772kb
input:
20480 1 1 d 1 2 d 1 1 z 1 2 z 2 1 pp 2 2 pp 2 3 pp 2 1 zp 2 2 zp 2 3 zp 2 1 pz 2 2 pz 2 3 pz 2 1 zz 2 2 zz 2 3 zz 3 1 www 3 2 www 3 3 www 3 4 www 3 1 mww 3 2 mww 3 3 mww 3 4 mww 3 1 wmw 3 2 wmw 3 3 wmw 3 4 wmw 3 1 mmw 3 2 mmw 3 3 mmw 3 4 mmw 3 1 wwm 3 2 wwm 3 3 wwm 3 4 wwm 3 1 mwm 3 2 mwm 3 3 mwm 3 ...
output:
2 3 2 3 3 4 5 3 4 5 3 4 5 3 4 5 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 5 6 7 8 9 5 6 7 8 9 5 6 7 8 9 4 6 7 8 9 5 6 7 8 9 5 5 7 8 9 5 6 7 8 9 5 6 7 8 9 5 6 7 8 9 5 6 7 8 9 5 5 7 8 9 5 6 7 8 9 4 6 7 8 9 5 6 7 8 9 5 6 7 8 9 5 6 7 8 9 6 7 8 9 10 11 6 7 8 9 10 11 6 7 8 9 10 11 5 ...
result:
ok 20480 numbers
Test #9:
score: 0
Accepted
time: 219ms
memory: 15664kb
input:
2000 88 14 hbwgbmjtqmgdpbgsdkjndhwjrhluountepcjpecnaogiamrzmnomjcgzzvdrzsfjspyxpooxhjtzlqtzvpeydwap 104 88 osirzoiablktpnobqvhckmttlpbgaeakzhemoxgteqbkmfzaerhqfwkoqpsiqqymmbmufxhvfhovkhdduzybzzhqnvbmswqepkqzrkox 82 25 rumtzeygumtvcmyiowwmxkjekajxpubgazyxabibdirnbsmzsjawtaksrydmuroohkrrajlqqyxogtvuul...
output:
31 177 53 71 113 9 153 107 97 51 149 153 121 193 111 38 129 175 99 183 91 183 115 182 203 41 193 155 159 11 149 145 111 19 76 152 67 107 79 15 49 175 149 63 115 59 45 39 138 37 102 14 23 157 75 175 31 33 65 95 171 61 59 34 73 107 195 185 113 11 65 16 128 184 59 139 23 131 115 135 143 166 42 34 49 29...
result:
ok 2000 numbers
Test #10:
score: 0
Accepted
time: 769ms
memory: 47280kb
input:
1 200000 100 cbdadabcbdaaacbedaccdeeeaabececdbcdebcedaeacddcdeaacaccedeadecacaabbdbdbbbbbeaecddbcaaeeaddcabcbebecebcddeccaeceacdebecaddcaddaaadaecabcbbbababedbbccbaceadaeccbbceaeacdccaaaabcbdaebcbcacaaeebebdddeeeeddcaaadbbbccacecacccebeeaabaecbdeccccbdbeedcddececabeaadeaadadcccbeebaecbacbccdbaceebdb...
output:
222
result:
ok 1 number(s): "222"
Test #11:
score: 0
Accepted
time: 792ms
memory: 47256kb
input:
1 200000 100 bcacdaadcdbcaeeebacabdaadebbceabaacdebddeacdebaabdccacdcacadbceceecdccebdebdbccdadbebbaebcabeddeabbdebdadcdedaadedbccbbdbcccdceddeadccdaadeecbebddcddccccbebccbbadaaadeeabaedecdacbeaabadcdeaeddadecdeddbeedeccaabaeebebdbecceaecbdcebceaadeebeaaceadebedcbdbdbcdbbecabddecabcdbccbbbecdaceabdd...
output:
220
result:
ok 1 number(s): "220"
Extra Test:
score: 0
Extra Test Passed