Submission #1008515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008515		Alihan_8	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	224 ms	33700 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int Mod = 1e9 + 7, P = 31;

struct _hash{
    vector <int> pw, p;

    int n;

    _hash() : pw(1, 1) {}

    void modify(string s){
        int n = s.size();

        while ( pw.size() <= n ){
            pw.pb(pw.back() * P % Mod);
        }

        p.resize(n + 1);

        for ( int i = 0; i < n; i++ ){
            p[i + 1] = (p[i] * P + s[i] - 'a' + 1) % Mod;
        }
    }

    int get(int l, int r){
        return (p[r + 1] - p[l] * pw[r - l + 1] % Mod + Mod) % Mod;
    }
};

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

    int t; cin >> t;

    while ( t-- ){
        string s; cin >> s;

        _hash h;

        h.modify(s);

        int l = 0, r = (int)s.size() - 1, ans = 0;

        while ( l <= r ){
            if ( l == r ){
                ans++;

                break;
            }

            int p = l, q = r;

            while ( p < q && h.get(l, p) != h.get(q, r) ){
                p++, q--;
            }

            if ( p < q ){
                ans += 2;
            } else{
                ans++;

                break;
            }

            l = p + 1, r = q - 1;
        }

        cout << ans << ln;
    }

    cout << '\n';
}

Compilation message (stderr)

palindromic.cpp: In member function 'void _hash::modify(std::string)':
palindromic.cpp:43:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   43 |         while ( pw.size() <= n ){
      |                 ~~~~~~~~~~^~~~

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