oj.uz

Submission #48155

# Submission time Handle Problem Language Result Execution time Memory
48155 2018-05-10T11:16:55 Z kyaryunha Palindromes (APIO14_palindrome) C++17
0 / 100
 1000 ms 3564 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 317 ms 1420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 1996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 2308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 3564 KB Time limit exceeded
2 Halted 0 ms 0 KB -