Submission #912517

#	Time	Username	Problem	Language	Result	Execution time	Memory
912517		MisterReaper	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	230 ms	17048 KiB

palindromic

#include <bits/stdc++.h>
using i64 = long long;

/**
 * Description: Modular arithmetic operations basic
 * Source: MisterReaper
 * KACTL:
 * Not. 
 */

constexpr int MOD = 1E9 + 7;
constexpr int PRIME = 37;

int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}

int add(int a, int b) {
    return (a + b) % MOD;
}

int sub(int a, int b) {
    return add(a, MOD - b);
}

int expo(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) {
            res = mul(res, a);
        }

        a = mul(a, a);
        b >>= 1;
    }

    return res;
}

int inv(int a) {
    return expo(a, MOD - 2);
}

int divide(int a, int b) {
    return mul(a, inv(b));
}

#define ONLINE_JUDGE
void solve() {
    std::string s;
    std::cin >> s;

    int n = s.size();
    s = '$' + s;

    std::vector<int> hash(n + 1);
    int ans = 0, l = 1, r = n;
    while(l <= r) {
        if(l == r) {
            ans++;
            break;
        }

        //std::cerr << l << " " << r << "\n";
        int h1 = 0, h2 = 0, len = 0;
        while(l < r) {
            h1 = add(mul(h1, PRIME), s[l] - 'a' + 1);
            h2 = add(h2, mul(s[r] - 'a' + 1, expo(PRIME, len)));

            if(h1 == h2) {
                break;
            }

            l++; 
            r--;
            len++;
        }

        if(h1 == h2) {
            ans += 2;
        } else {
            ans++;
            break;
        }

        l++;
        r--;
    }

    std::cout << ans << "\n";
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int t = 1; std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

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