Submission #668897

#	Time	Username	Problem	Language	Result	Execution time	Memory
668897		Dan4Life	Palindromes (APIO14_palindrome)	C++17	23 / 100	1091 ms	37820 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) a.begin(),a.end()
const int maxn = 1e6+10;
const int MOD = 1e9+7;

int pw[maxn], h[maxn], h2[maxn], A = 9973;
string s;
unordered_map<int,int> M;
void comp_hash(string s, int h[])
{
    h[0] = 1;
    for(int i = 0; i < (int)s.size(); i++)
        h[i+1] = ((h[i]*A)%MOD+s[i])%MOD;
}
 
int get_hash(int a, int b, int h[]){
    return (h[b+1]-(h[a]*pw[b-a+1])%MOD+MOD)%MOD;
}
 
int mir(int ind){return (int)s.size()-ind-1;}
int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> s; pw[0] = 1;
    for(int i = 1; i<maxn; i++) pw[i] = (pw[i-1]*A)%MOD;
    int ans = 0, n = (int)s.size();
    comp_hash(s,h); reverse(all(s)); comp_hash(s,h2); reverse(all(s));
    for(int i = 0; i < n; i++) 
        for(int j = i; j < n; j++)
            M[get_hash(i,j,h)]+=j-i+1;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            int mid = (i+j)/2;
            if(i!=j and get_hash(i,mid-(j-i+1)%2,h)
            !=get_hash(mir(j),mir(mid+1),h2)) continue;
            ans = max(ans, M[get_hash(i,j,h)]);
        }
    }
    cout << ans << "\n";
}

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