Submission #1171383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171383		freezecode	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	0 ms	320 KiB

palindromic

#include <iostream>
#include <vector> 
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <queue>
#include <unordered_set>
#include <sstream>
#include <cstdint>
#include <unordered_map>
#define nl '\n'
#define ll long long
#define COLOR_RESET "\033[0m"
#define COLOR_BLUE "\033[34m"
#define COLOR_GREEN "\033[32m"
using namespace std;

const ll MOD = 1e9+7;
const ll MOD2 = 1e9+9;

struct triple {
    int x;
    int y;
    int z;

    triple() {};
    triple(int x, int y, int z) : x(x), y(y), z(z) {};
};

std::ostream& operator<<(std::ostream& s, const pair<int, int>& t) { 
    s << "(" << t.first << ", " << t.second << ")";
    return s;
}

std::ostream& operator<<(std::ostream& s, const triple& t) { 
    s << "(" << t.x << ", " << t.y << ", " << t.z << ")";
    return s;
}

template<typename T>
std::ostream& operator<<(std::ostream& s, const std::vector<T>& t) { 
    int last = t.size() - 1;
    s << "[";
    for (int i = 0; i < t.size(); i++) {
        s << t[i];
        if (i != last) {
            s << ", ";
        }
    }
    return s << "]";
}

template<typename T, typename K>
std::ostream& operator<<(std::ostream& s, const pair<T, K>& t) { 
    s << "(" << t.first << ", " << t.second << ")";
    return s;
}

string arrToString(int* arr, int size) {
    std::ostringstream result;  
    result << "[";              
    for (int i = 0; i < size; ++i) {
        result << arr[i];       
        if (i != size - 1) {
            result << ", ";   
        }
    }
    result << "]";              
    return result.str(); 
}



ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % MOD;
            res %= MOD;
        a = a % MOD * a % MOD;
        a %= MOD;
        b >>= 1;
    }
    return res % MOD;
}

bool isPrime(int k) {
    if (k == 1) {
        return false;
    }
    for (int i = 2; i * i <= k; i++) {
        if (k % i == 0) {
            return false;
        }
    }
    return true;
}

ll compute_hash(string const& s, int m) {
    const int p = 31;
    ll hash_value = 0;
    ll p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}
 
int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
 
int mod_inverse(int a) {
    int x, y;
    int g = gcd(a, MOD, x, y);
    x = (x % MOD + MOD) % MOD;
    return x;
}


void compute_power_inverses(vector<ll>& inv, ll p) {
    inv[0] = 1;
    inv[1] = mod_inverse(p);
    for (int i = 2; i < inv.size(); i++) {
        inv[i] = inv[i - 1] * inv[1] % MOD;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    const int P1 = 31;
    const int P2 = 33;
    while (t--) {
        string s;
        cin >> s;
        int len = s.size();
        ll prefix_hash1 = 0, suffix_hash1 = 0, prefix_hash2 = 0, suffix_hash2 = 0;
        ll suffix_pow1 = 1, suffix_pow2 = 1;
        int l = 0, r = len - 1;
        int count = 1;
        while (l < r) {
            suffix_pow1 = suffix_pow1 * P1 % MOD;
            suffix_pow2 = suffix_pow2 * P2 % MOD2;
            prefix_hash1 = prefix_hash1 * P1 + (s[l] - 'a') * P1 % MOD;
            prefix_hash2 = prefix_hash2 * P2 + (s[l] - 'a') * P2 % MOD2;
            suffix_hash1 += (s[r] - 'a') * suffix_pow1;
            suffix_hash2 += (s[r] - 'a') * suffix_pow2;
            if (prefix_hash1 == suffix_hash1 && prefix_hash2 == suffix_hash2) {
                count += 2;
                prefix_hash1 = prefix_hash2 = 0;
                suffix_hash1 = suffix_hash2 = 0;
                suffix_pow1 = suffix_pow2 = 1;
                if (l == r - 1) {
                    count--;
                }
            }
            l++; r--;
        }
        cout << count << nl;
    }
}
    

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