제출 #997365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997365		vjudge1	회문 (APIO14_palindrome)	C++17	8 / 100	1070 ms	5612 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll mod[2] = {ll(1e9 + 7), ll(1e9 + 9)};
const ll base[2] = {ll(727), ll(1e6 + 1)};
const ll N = 3e5 + 10;

string s;
ll n, base_pwr[2][N], inv[2];

ll pwr(ll a, ll b, ll id){
    if (b < 0) return 0;
    if (b == 0) return 1;

    ll val = pwr(a, b / 2, id);
    val *= val;
    val %= mod[id];

    if (b % 2) val *= a;
    return val % mod[id];
}

int main(){
    for (ll j = 0; j < 2; j ++){
        base_pwr[j][0] = 1;
        inv[j] = pwr(base[j], mod[j] - 2, j);
        for (ll i = 1; i < N; i ++)
            base_pwr[j][i] = base_pwr[j][i - 1] * base[j] % mod[j];
    }

    cin >> s;
    n = s.size();

    // ll l = 0;
    // ll r = n + 1;

    // while (r - l > 1){
    //     ll mid = (l + r) / 2;
    //     ll len = 2 * mid;
        
    //     if (len > n){
    //         r = mid;
    //         continue;
    //     }

    //     ll hsh0[2] = {0}, hsh[2] = {0};
    //     map<pair<ll, ll>, ll> cnt;
    
    //     ll mx_occur = 0;
    //     for (ll i = 0; i < len; i ++){
    //         for (ll j = 0; j < 2; j ++){
    //             hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
    //             hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
    //         }
    //     }

    //     if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
    //         cnt[{hsh[0], hsh[1]}]++;
    //         mx_occur = 1;
    //     }

    //     for (ll i = 1; i + len - 1 < n; i ++){
    //         for (ll j = 0; j < 2; j ++){
    //             hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
    //             hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
    //             hsh[j] = (hsh[j] + mod[j]) % mod[j];

    //             hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; 
    //             hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
    //             hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
    //         }

    //         if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
    //             cnt[{hsh[0], hsh[1]}]++;
    //             mx_occur = max(mx_occur, cnt[{hsh[0], hsh[1]}]);
    //         }
    //     }

    //     // cout << len << " -- " << mx_occur << endl;

    //     if (mx_occur >= len)
    //         l = mid;
    //     else 
    //         r = mid;
    // }

    ll ans = 0;
    // for (ll len = max(1ll, l - 4); len <= min(l + 4, n); len += 2){
    //     ll hsh0[2] = {0}, hsh[2] = {0};
    //     map<pair<ll, ll>, ll> cnt;
    
    //     ll mx_occur = 0;
    //     for (ll i = 0; i < len; i ++){
    //         for (ll j = 0; j < 2; j ++){
    //             hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
    //             hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
    //         }
    //     }

    //     if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
    //         cnt[{hsh[0], hsh[1]}]++;
    //         mx_occur = 1;
    //     }

    //     for (ll i = 1; i + len - 1 < n; i ++){
    //         for (ll j = 0; j < 2; j ++){
    //             hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
    //             hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
    //             hsh[j] = (hsh[j] + mod[j]) % mod[j];

    //             hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; 
    //             hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
    //             hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
    //         }

    //         if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
    //             cnt[{hsh[0], hsh[1]}]++;
    //             mx_occur = max(mx_occur, cnt[{hsh[0], hsh[1]}]);
    //         }
    //     }

    //     ans = max(ans, len * mx_occur);
    // }

    // l = 1;
    // r = n + 1;

    // while (r - l > 1){
    //     ll mid = (l + r) / 2;
    //     ll len = 2 * mid - 1;
        
    //     if (len > n){
    //         r = mid;
    //         continue;
    //     }

    //     ll hsh0[2] = {0}, hsh[2] = {0};
    //     map<pair<ll, ll>, ll> cnt;
    
    //     ll mx_occur = 0;
    //     for (ll i = 0; i < len; i ++){
    //         for (ll j = 0; j < 2; j ++){
    //             hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
    //             hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
    //         }
    //     }

    //     if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
    //         cnt[{hsh[0], hsh[1]}]++;
    //         mx_occur = 1;
    //     }

    //     for (ll i = 1; i + len - 1 < n; i ++){
    //         for (ll j = 0; j < 2; j ++){
    //             hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
    //             hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
    //             hsh[j] = (hsh[j] + mod[j]) % mod[j];

    //             hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; 
    //             hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
    //             hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
    //         }

    //         if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
    //             cnt[{hsh[0], hsh[1]}]++;
    //             mx_occur = max(mx_occur, cnt[{hsh[0], hsh[1]}]);
    //         }
    //     }

    //     // cout << len << " -- " << mx_occur << endl;

    //     if (mx_occur >= len)
    //         l = mid;
    //     else 
    //         r = mid;
    // }

    // for (ll len = max(1ll, l - 4); len <= min(l + 4, n); len += 2){
    //     ll hsh0[2] = {0}, hsh[2] = {0};
    //     map<pair<ll, ll>, ll> cnt;
    
    //     ll mx_occur = 0;
    //     for (ll i = 0; i < len; i ++){
    //         for (ll j = 0; j < 2; j ++){
    //             hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
    //             hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
    //         }
    //     }

    //     if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
    //         cnt[{hsh[0], hsh[1]}]++;
    //         mx_occur = 1;
    //     }

    //     for (ll i = 1; i + len - 1 < n; i ++){
    //         for (ll j = 0; j < 2; j ++){
    //             hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
    //             hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
    //             hsh[j] = (hsh[j] + mod[j]) % mod[j];

    //             hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; 
    //             hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
    //             hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
    //         }

    //         if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
    //             cnt[{hsh[0], hsh[1]}]++;
    //             mx_occur = max(mx_occur, cnt[{hsh[0], hsh[1]}]);
    //         }
    //     }

    //     ans = max(ans, len * mx_occur);
    // }

    for (ll len = max(1ll, n - 100); len <= n; len ++){
        ll hsh0[2] = {0}, hsh[2] = {0};
        map<pair<ll, ll>, ll> cnt;
    
        ll mx_occur = 0;
        for (ll i = 0; i < len; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
            }
        }

        if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
            cnt[{hsh[0], hsh[1]}]++;
            mx_occur = 1;
        }

        for (ll i = 1; i + len - 1 < n; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
                hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
                hsh[j] = (hsh[j] + mod[j]) % mod[j];

                hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; 
                hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
            }

            if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
                cnt[{hsh[0], hsh[1]}]++;
                mx_occur = max(mx_occur, cnt[{hsh[0], hsh[1]}]);
            }
        }

        ans = max(ans, len * mx_occur);
    }

    for (ll len = 1; len <= min(100ll, n); len ++){
        ll hsh0[2] = {0}, hsh[2] = {0};
        map<pair<ll, ll>, ll> cnt;
    
        ll mx_occur = 0;
        for (ll i = 0; i < len; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
            }
        }

        if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
            cnt[{hsh[0], hsh[1]}]++;
            mx_occur = 1;
        }

        for (ll i = 1; i + len - 1 < n; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
                hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
                hsh[j] = (hsh[j] + mod[j]) % mod[j];

                hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; 
                hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
            }

            if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
                cnt[{hsh[0], hsh[1]}]++;
                mx_occur = max(mx_occur, cnt[{hsh[0], hsh[1]}]);
            }
        }

        ans = max(ans, len * mx_occur);
    }

    for (ll len = max(1ll, (ll)sqrt(n) - 100ll); len <= min((ll)sqrt(n) + 100ll, n); len ++){
        ll hsh0[2] = {0}, hsh[2] = {0};
        map<pair<ll, ll>, ll> cnt;
    
        ll mx_occur = 0;
        for (ll i = 0; i < len; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
            }
        }

        if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
            cnt[{hsh[0], hsh[1]}]++;
            mx_occur = 1;
        }

        for (ll i = 1; i + len - 1 < n; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
                hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
                hsh[j] = (hsh[j] + mod[j]) % mod[j];

                hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; 
                hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
            }

            if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
                cnt[{hsh[0], hsh[1]}]++;
                mx_occur = max(mx_occur, cnt[{hsh[0], hsh[1]}]);
            }
        }

        ans = max(ans, len * mx_occur);
    }

    cout << ans << endl;
}

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