Submission #48155

#	Time	Username	Problem	Language	Result	Execution time	Memory
48155		kyaryunha	Palindromes (APIO14_palindrome)	C++17	0 / 100	1085 ms	3564 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int A[300005];
string s,imsi;
int ssiz,dap,isiz;
map<string,pii> mp;
void manachers(string S,int N)
{
    int r = 0, p = 0;
    for(int i=0;i<N;i++)
    {
        if(i<=r) A[i]=min(A[2*p-1],r-i);
        else A[i]=0;
        while(i-A[i]-1>=0&&i+A[i]+1<N&&S[i-A[i]-1]==S[i+A[i]+1]) A[i]++;
        if(i+A[i]>r)
        {
            r=i+A[i];
            p=i;
        }
    }
}
int main(void)
{
    cin >> imsi;
    isiz = imsi.size();
    s+='#';
    for(int i=0;i<isiz;i++)
    {
        s+=imsi[i];
        s+='#';
    }
    ssiz = s.size();
    manachers(s,ssiz);
    for(int i=1;i<ssiz;i+=2)
    {
        string now;
        for(int j=i-A[i]+1;j<=i+A[i]-1;j+=2) now+=s[j];
        int nsiz = now.size();
        for(int j=nsiz;j>=0;j-=2)
        {
            //printf("%s\n",now.c_str());
            mp[now].second=now.size();
            mp[now].first++;
            string newnow;
            for(int i=1;i<nsiz-1;i++)
            {
                newnow=now[i];
            }
            now=newnow;
        }
    }
    map<string,pii>::iterator iter;
    for(iter=mp.begin();iter!=mp.end();iter++)
    {
        int score = (*iter).second.first*(*iter).second.second;
        dap = max(dap,score);
    }
    printf("%d",dap);
}

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