Submission #45290

#	Time	Username	Problem	Language	Result	Execution time	Memory
45290		nickyrio	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	170 ms	19828 KiB

palindromic

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 1001000
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;

const long long MOD = 1e9 + 7, base = 29;
string st;
int n;
long long Hash[N], POW[N];

void InitHash() {
    Hash[0] = 0;
    FOR(i, 1, n) Hash[i] = (Hash[i - 1] * base + st[i] - 'a') % MOD;
}

long long GetHash(int i, int j) {
    return (Hash[j] - Hash[i - 1] * POW[j - i + 1] % MOD + MOD * MOD) % MOD;
}

int Go(int l, int r) {
    //DEBUG(l);DEBUG(r);
    if (l == r) return 1;
    if (l > r) return 0;
    FOR(len, 1, r - l + 1) {
        if (l + len - 1 >= r - len + 1) break;
        //DEBUG(len);
        //DEBUG(GetHash(l, l + len - 1));
        //DEBUG(GetHash(r - len + 1, r));
        if (GetHash(l, l + len - 1) == GetHash(r - len + 1, r)) return 2 + Go(l + len, r - len);
    }
    return 1;
}

void solve() {
    cin >> st;
    n = st.size();
    st = '~' + st;
    InitHash();
    cout << Go(1, n) << '\n';
}
int main() {
    #ifdef NERO
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    double stime = clock();
    #else 
        //freopen(taskname".inp","r",stdin);
        //freopen(taskname".out","w",stdout);
    #endif //NERO
    IO;
    POW[0] = 1;
    FOR(i, 1, N - 1) POW[i] = POW[i - 1] * base % MOD;
    int test;
    cin >> test;
    while (test--) solve();
    #ifdef NERO
    double etime = clock();
    cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n";
    #endif // NERO
}

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