Submission #973902

#TimeUsernameProblemLanguageResultExecution timeMemory
973902sleepntsheepSavez (COCI15_savez)C11
120 / 120
376 ms25236 KiB
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h> unsigned rand_wide() { return 1llu * rand()*rand(); } unsigned rand_wide2(unsigned l, unsigned r) { if (l==r)return l; return l+rand_wide()%(r-l); } #define N 1000000 #define TN 2000000 #define N_ (TN+N+100) char s[N_]; int p, n, z, at[N+1], hash[N_], BASE, MOD = 1000000007; int power(int a,int b) { if (!b)return 1; int r= power(a,b/2); if(b&1)return r*1ll*r%MOD*a%MOD; return r*1ll*r%MOD; } int K[TN+1], B[TN+1], L[TN+1], R[TN+1], V[TN+1], alc; int tnode(int x,int y) { int p=++alc; K[p]=x; B[p]=rand_wide(); L[p]=R[p]=0; V[p]=y; return p; } void split(int v,int*l,int*r,int k) { if(!v){*l=*r=0;return;} if(K[v]<=k) split(R[v],R+v,r,k),*l=v; else split(L[v],l,L+v,k),*r=v; } void merge(int*v,int l,int r) { if(!l||!r){*v=l^r;return;} if(B[l]>B[r]) merge(R+l,R[l],r),*v=l; else merge(L+r,l,L[r]),*v=r; } void put(int*v,int key,int val) { int t1,t2,t3; split(*v,&t2,&t3,key); split(t2,&t1,&t2,key-1); if(!t2) t2=tnode(key,val); else if(val>V[t2])V[t2]=val; merge(&t2,t1,t2); merge(v,t2,t3); } int get(int v,int key) { while(v&&K[v]!=key) { if(K[v]<key)v=R[v]; else v=L[v]; } return V[v]; } int main() { srand(time(0)); BASE = rand_wide2(200, MOD-1); scanf("%d", &n); for (int len, i = 0; i < n; ++i) scanf("%s", s+(at[i]=p)), at[i+1]=p+=strlen(s+at[i])+1; for (int i=0;i<n;++i) for(int bp=1,j=at[i];s[j];++j,bp=bp*1ll*BASE%MOD) hash[j] = bp * 1ll * s[j]%MOD; for (int i=1;i<=at[n];++i) if(s[i]>0) hash[i]=(hash[i]+hash[i-1])%MOD; for(int map=0,dp, j, i=n-1;i>=0;--i) { dp=get(map,hash[at[i+1]-2])+1; for(j=1;j<=at[i+1]-at[i]-1;++j) { if(hash[at[i]+j-1]*1ll*power(BASE,at[i+1]-1-at[i]-j)%MOD==(hash[at[i+1]-2]+MOD-hash[at[i+1]-2-j])%MOD) put(&map,hash[at[i]+j-1],dp); } if(dp>z)z=dp; } printf("%d",z); }

Compilation message (stderr)

savez.c: In function 'main':
savez.c:77:14: warning: unused variable 'len' [-Wunused-variable]
   77 |     for (int len, i = 0; i < n; ++i)
      |              ^~~
savez.c:76:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d", &n);
      |     ^~~~~~~~~~~~~~~
savez.c:78:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%s", s+(at[i]=p)), at[i+1]=p+=strlen(s+at[i])+1;
      |         ^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...