Submission #36834

#	Time	Username	Problem	Language	Result	Execution time	Memory
36834		imaxblue	Palindromes (APIO14_palindrome)	C++14	0 / 100	1000 ms	11980 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, l   l>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

const ll seed=31;
ll po[600005]={1}, ans;
int n, r[600005], rit, c, k, x, y, p;
string s, t="#";
map<int, ll> m;
void add(int X, ll V){
    if (m.count(X)==0) m[X]=0;
    m[X]+=V;
}
int main(){
    fox1(l, 600001) po[l]=(po[l-1]*31)%MN;
    cin >> s;
    /*s="a";
    k=1;
    while(s.size()*2+1<100000){
        t=s;
        t+=(k+'a');
        t+=s;
        s=t;
        ++k;
    }*/
    //cout << s << endl;
    fox(l, s.size()){
        t+=s[l]; t+="#";
    }
    s=t;
    //cout << s << endl;
    n=s.size();
    fox(l, n){
        //if (l%1000==0) cout << l << endl;
        if (l>rit) r[l]=0;
        else r[l]=r[2*p-l];
        while(l-r[l]>0 && l+r[l]<n-1 && s[l-r[l]-1]==s[l+r[l]+1]) r[l]++;
        if (l+r[l]>rit){
            rit=l+r[l];
            p=l;
        }
        //cout << r[l] << ' ';
    }
    //cout << endl;
    rit=-1;
    fox(l, n){
        if (r[l]==0) continue;
        if (l+r[l]>rit){
            k=r[l]; p=l+k;
            while(1){
                //cout << k<< ' ' << p << endl;
                while(k>=r[l] && r[p]<k*2) k/=2;
                if (k<r[l]) break;
                k*=2; p+=k;
            }
            c=(p-l+r[l])/2/r[l];
            //continue;
            x=0; k=0;
            for(int l2=l-r[l]+1; l2<=l+r[l]-1; l2+=2){
                x=(seed*x+(s[l2]-'a'+1))%MN; ++k;
            }
            y=x;
            //cout << l << ' ' << p << ' ' << r[l] << ' ' << c << endl;
            fox1(l2, c){
                add(y, 1LL*(c-l2+1)*l2*r[l]);
                y=(y*po[k]+x)%MN;
                //if (y<10)cout << y << ' ';
            }
            rit=p+1;
        }
    }
    for(map<int, ll>::iterator i=m.begin(); i!=m.end(); ++i){
        ans=max(ans, i->y);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
palindrome.cpp:49:5: note: in expansion of macro 'fox'
     fox(l, s.size()){
     ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27