제출 #469242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
469242		amirmohammad_nezami	회문 (APIO14_palindrome)	C++14	23 / 100	1086 ms	7544 KiB

palindrome

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

#define F first
#define S second
#define PB push_back
#define ll long long
#define _sz(e) e.size()
#define pii pair <int , int>
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#pragma GCC target("sse4,avx,avx2")
#pragma GCC optimize("O3,unroll-loops")

const ll maxn = 1e5 + 8 , N = 200 + 8 , base = 301 , mod = 1e9 + 7 , INF = 1e18;

unordered_map <int , int> mp;

ll n , h[maxn] , hrev[maxn] , pbase[maxn];
string s;

void pre() {
    pbase[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        pbase[i] = (pbase[i - 1] * base) % mod;
    } 
    for (int i = 1; i <= n; ++i) {
        h[i] = (h[i - 1] * base + s[i - 1]) % mod;
    }
    for (int i = n; i >= 1; --i) {
        hrev[i] = (hrev[i + 1] * base + s[i - 1]) % mod;
    }
}

int HASH(int l , int r) {
    return (h[r] - (h[l] * pbase[r - l] % mod) + mod) % mod;
}

int HASHrev(int l , int r) {
    return (hrev[l + 1] - (hrev[r + 1] * pbase[r - l] % mod) + mod) % mod;
}

bool palindrome(int l , int r) {
    int mid = (l + r) / 2;
    if((r - l) & 1) {
        if(r - l == 1) return 1;
        return (HASH(l , mid) == HASHrev(mid + 1 , r));
    }
    return (HASH(l , mid) == HASHrev(mid , r));
}

int main() {
    FAST;
    cin >> s; n = _sz(s);
    pre();

    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if(!palindrome(i , j)) continue;
            // cout << i << ' ' << j << endl;
            mp[HASH(i , j)]++;
        }   
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if(!palindrome(i , j)) continue;
            ans = max(ans , 1ll * mp[HASH(i , j)] * (j - i));
        }
    }
    cout << ans << '\n';
}

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