제출 #669038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
669038		Dan4Life	Palindromes (APIO14_palindrome)	C++17	23 / 100	1079 ms	21712 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(a) a.begin(),a.end()
const int maxn = 1e4+10;
const int MOD = 1e9+7;
 
ll pw[maxn], h[maxn], h2[maxn], A = 9973;
string s;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
 
unordered_map<int, int, custom_hash> M, vis;

void comp_hash(string s, ll h[])
{
    h[0] = 1;
    for(int i = 0; i < (int)s.size(); i++)
        h[i+1] = ((h[i]*A)%MOD+s[i])%MOD;
}
 
inline int get_hash(int a, int b, ll h[]){
    return (h[b+1]-(h[a]*pw[b-a+1])%MOD+MOD)%MOD;
}
 
inline int mir(int ind){return (int)s.size()-ind-1;}
 
inline bool ispal(int i, int j){
    int mid = (i+j)/2; if(j>=(int)s.size()) return false;
    return(i==j or get_hash(i,mid-(j-i+1)%2,h)==get_hash(mir(j),mir(mid+1),h2));
}

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);
    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++){
        int l = 0, r = i;
        while(l<r){
            int mid = (l+r)/2;
            if(ispal(mid,i*2-mid)) r=mid;
            else l=mid+1;
        }
        r = i*2-l;
        while(l<=r and !vis[get_hash(l,r,h)] and ispal(l,r)){
            vis[get_hash(l,r,h)]=1; 
            ans = max(ans, M[get_hash(l,r,h)]);
            l++, r--;
        }

        if(i==n-1 or s[i]!=s[i+1]) continue;
        {
            int l = 0, r = i;
            while(l<r){
                int mid = (l+r)/2;
                if(ispal(mid,i*2-mid+1)) r=mid;
                else l=mid+1;
            }
            r = i*2-l+1;
            while(l<=r and !vis[get_hash(l,r,h)] and ispal(l,r)){
                vis[get_hash(l,r,h)]=1; 
                ans = max(ans, M[get_hash(l,r,h)]);
                l++, r--;
            }
        }
    }
    cout << ans << "\n";
}

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