Submission #662810

#	Time	Username	Problem	Language	Result	Execution time	Memory
662810		Kahou	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	553 ms	15052 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e6 + 50;
const int mod = 1e9 + 7;
const int B = 1742;
int n, h[N];
string s;

int add(int a, int b) {
        a += b;
        if (a >= mod) a -= mod;
        if (a < 0) a += mod;
        return a;
}
int mul(int a, int b) {
        return 1ll*a*b%mod;
}
int pw(int a, int b) {
        int out = 1;
        while (b) {
                if(b&1) out = mul(out, a);
                a = mul(a,a);
                b>>=1;
        }
        return out;
}
int H(int l, int r) {
        return add(h[r], -mul(h[l], pw(B, r-l)));
}

void solve() {
        cin >> s;
        n = s.size();
        for (int i = 1; i <= n; i++) {
                h[i] = add(mul(h[i-1], B), s[i-1]);
        }
        int l = 0;
        int ans = 0;
        for (int r = 1; r <= n-l; r++) {
                if (H(l, r) == H(n-r, n-l)) {
                        ans += 2-(r == n-l);
                        l = r;
                }
        }
        cout << ans << endl;
}
int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int tc;
        cin >> tc;
        while(tc--) 
                solve();
        return 0;
}

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