Submission #135116

#TimeUsernameProblemLanguageResultExecution timeMemory
135116wilwxkPalindromes (APIO14_palindrome)C++14
0 / 100
315 ms7692 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=3e5+5; const ll MOD=1e9+9; const ll P=257; char c[MAXN]; ll h[MAXN], rh[MAXN]; ll pot[MAXN]; int n; ll respf=0; ll ghash(int ini, int fim) { ll val=0; if(ini<=fim) { if(ini!=0) val=h[ini-1]; val*=pot[fim-ini+1]; val%=MOD; val=h[fim]-val; while(val<0) val+=MOD; } else { if(ini!=n-1) val=rh[ini+1]; val*=pot[ini-fim+1]; val%=MOD; val=rh[fim]-val; while(val<0) val+=MOD; } return val; } ll testa(int k) { if(k<=0) return k; if(k>n) return n-k; int resp=0; // printf("testing %d\n", k); map<ll, int> mp; for(int i=k-1; i<n; i++) { int ind=i-k+1; ll val=ghash(ind, i); // printf(" %d: %lld %lld\n", i, val, ghash(i, ind)); if(val==ghash(i, ind)) { mp[val]++; resp=max(resp, mp[val]); } } return (ll)resp*k; } void precalc() { pot[0]=1; for(int i=1; i<=n; i++) pot[i]=(pot[i-1]*P)%MOD; for(int i=0; i<n; i++) { if(i!=0) h[i]=(h[i-1]*P)%MOD; h[i]+=(c[i]-'a'); h[i]%=MOD; } for(int i=n-1; i>=0; i--) { if(i!=n-1) rh[i]=(rh[i+1]*P)%MOD; rh[i]+=(c[i]-'a'); rh[i]%=MOD; } } int main() { scanf(" %s", c); n=strlen(c); precalc(); // for(int i=1; i<=n; i++) { // printf("testa %d >> %lld\n", i, testa(i)); // respf=max(respf, testa(i)); // } int val=1; while(val<n) val*=2; int opt=1, opt2=0; for(int i=val; i>0; i/=2) { // printf("add %d\n", i); // while(testa(opt+i-2)<=testa(opt+i)) opt+=i, printf("opt1 %d\n", opt); // while(testa(opt2+i-2)<=testa(opt2+i)) opt2+=i, printf("opt2 %d\n", opt2); while(testa(opt+i-1)<=testa(opt+i)) opt+=i; while(testa(opt2+i-1)<=testa(opt2+i)) opt2+=i; } // printf("opt %d %d\n", opt, opt2); for(int i=opt-10; i<=opt+10; i++) respf=max(respf, testa(opt+i)); for(int i=opt2-10; i<=opt2+10; i++) respf=max(respf, testa(opt2+i)); printf("%lld\n", respf); }

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", c); n=strlen(c);
  ~~~~~^~~~~~~~~~
#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...