제출 #738220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
738220		study	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	1457 ms	28496 KiB

palindromic

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

const int mod = 1e9+9, hash_val = 31, N = 1e6;

int hashn[N],pow31[N];

int power(int a, int b){
    int ans = 1;
    while (b){
        if (b&1) ans = (ans*a)%mod;
        a = (a*a)%mod;
        b >>= 1;
    }
    return ans;
}

int inv(int a){
    return power(a,mod-2);
}

int calc(int l, int r){
    if (l > r) return 0;
    int ans = hashn[r];
    if (l != 0) ans -= hashn[l-1];
    return (((ans+mod)%mod)*inv(pow31[l]))%mod;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
    pow31[0] = 1;
    for (int i=1; i<1e6; ++i){
        pow31[i] = (pow31[i-1]*hash_val)%mod;
    }
	int t;
    cin >> t;
    while (t--){
        string s;
        cin >> s;
        int ans = 0, res = 1, n = s.size(), l = 0, r = n-1;
        hashn[0] = s[0]-'a'+1;
        for (int i=1; i<n; ++i){
            hashn[i] = hashn[i-1]+pow31[i]*(s[i]-'a'+1);
            hashn[i] %= mod;
        }
        while (l < r){
            int L = l, R = r;
            while ((calc(L,l-1) != calc(r+1,R) or l == L) and l < r){
                l++; r--;
            }
            if (calc(L,l-1) != calc(r+1,R)) break;
            ans += 2;
            if (l <= r) res = max(res,ans+1);
            else res = max(res,ans);
        }
        cout << res << '\n';
    }
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40