Submission #1171405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171405		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;

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, const int MOD) {
    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, const int P, const int MOD) {
    ll hash_value = 0;
    ll p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % MOD;
        p_pow = (p_pow * P) % MOD;
    }
    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, const int MOD) {
    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, const int MOD) {
    inv[0] = 1;
    inv[1] = mod_inverse(p, MOD);
    for (int i = 2; i < inv.size(); i++) {
        inv[i] = inv[i - 1] * inv[1] % MOD;
    }
}

struct string_hash {
    const int P[3] = {31, 33, 53};
    const int MOD[3] = {(int) 1e9 + 7, (int) 1e9 + 9, (int) 1e9 + 39};
    int inv[3];
    ll pow[3] = {1, 1, 1};
    ll hash_values[3] = {0, 0, 0};

    string_hash() {
        for (int i = 0; i < 3; i++) {
            inv[i] = mod_inverse(P[i], MOD[i]);
        }
    }

    bool operator==(string_hash& h) {
        return hash_values[0] == h.hash_values[0] && hash_values[1] == h.hash_values[1] && hash_values[2] == h.hash_values[2];
    }

    void removeFirst(char c) {
        for (int i = 0; i < 3; i++) {
            hash_values[i] = (((hash_values[i] - (c - 'a' + 1) * pow[i]) % MOD[i]) + MOD[i]) % MOD[i];
            pow[i] = pow[i] * inv[i] % MOD[i];
        }
    }

    void removeLast(char c) {
        for (int i = 0; i < 3; i++) {
            hash_values[i] = (((hash_values[i] - (c - 'a' + 1)) % MOD[i]) + MOD[i]) % MOD[i];
            hash_values[i] = hash_values[i] * inv[i] % MOD[i];
            pow[i] = pow[i] * inv[i] % MOD[i];
        }
    }

    void addFirst(char c) {
        for (int i = 0; i < 3; i++) {
            pow[i] = pow[i] * P[i] % MOD[i];
            hash_values[i] += (c - 'a' + 1) * pow[i];
        }
    }

    void addLast(char c) {
        for (int i = 0; i < 3; i++) {
            pow[i] = pow[i] * P[i] % MOD[i];
            hash_values[i] = (hash_values[i] * P[i] % MOD[i] + (c - 'a' + 1) * P[i]) % MOD[i];
        }
    }   

    void clear() {
        for (int i = 0; i < 3; i++) {
            hash_values[i] = 0;
            pow[i] = 1;
        }
    }
};

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

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

    int t;
    cin >> t;
    const int P1 = 31;
    const int P2 = 33;
    while (t--) {
        string s;
        cin >> s;
        int len = s.size();
        int l = 0, r = len - 1;
        string_hash prefix_hash, suffix_hash;
        int count = 1;
        while (l < r) {
            prefix_hash.addLast(s[l]);
            suffix_hash.addFirst(s[r]);
            if (prefix_hash == suffix_hash) {
                count += 2;
                prefix_hash.clear();
                suffix_hash.clear();
                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