Submission #668993

#	Time	Username	Problem	Language	Result	Execution time	Memory
668993		Dan4Life	회문 (APIO14_palindrome)	C++17	23 / 100	1053 ms	2540 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;

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;
    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 l = n; l >= 1; l--){
        for(int i = 0; i+l-1 < n; i++){
            int j = i+l-1;
            if(ans > (j-i+1)*(n-(j-i+1)+1)) break; 
            if(!ispal(i,j)) continue;
            M[get_hash(i,j,h)]+=j-i+1;
            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