oj.uz

Submission #534686

# Submission time Handle Problem Language Result Execution time Memory
534686 2022-03-08T14:01:05 Z alextodoran Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 125 ms 24700 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 1000000;

const int MOD = (int) 1e9 + 7;

int pwr (const int &a, const int &b) {
    if (b == 0) {
        return 1;
    } else if (b & 1){
        return (ll) a * pwr(a, (b ^ 1)) % MOD;
    } else {
        int aux = pwr(a, (b >> 1));
        return (ll) aux * aux % MOD;
    }
}
int inv (const int &a) {
    return pwr(a, MOD - 2);
}

int n;
string s;

int pw[N_MAX + 2];
int ipw[N_MAX + 2];
void precalc () {
    pw[0] = 1; pw[1] = 26;
    ipw[0] = 1; ipw[1] = inv(26);
    for (int i = 2; i < N_MAX; i++) {
        pw[i] = (ll) pw[i - 1] * pw[1] % MOD;
        ipw[i] = (ll) ipw[i - 1] * ipw[1] % MOD;
    }
}

int pref[N_MAX + 2];
void init () {
    for (int i = 1; i <= n; i++) {
        pref[i] = (pref[i - 1] + (ll) pw[i - 1] * (int) (s[i] - 'a')) % MOD;
    }
}
int query (int l, int r) {
    return (ll) (pref[r] - pref[l - 1] + MOD) * ipw[l - 1] % MOD;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    precalc();

    int t;
    cin >> t;
    while (t--) {
        cin >> s; n = (int) s.size();
        s = " " + s;
        init();
        int answer = 1;
        int l1 = 1, r1 = 1;
        int l2 = n, r2 = n;
        while (r1 < l2) {
            if (query(l1, r1) == query(l2, r2)) {
                answer += 2;
                if (l2 - r1 == 1) {
                    answer -= 1;
                }
                l1 = r1 = r1 + 1;
                l2 = r2 = l2 - 1;
            } else {
                r1++;
                l2--;
            }
        }
        cout << answer << "\n";
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8140 KB Output is correct
2 Correct 9 ms 8140 KB Output is correct
3 Correct 9 ms 8152 KB Output is correct
4 Correct 11 ms 8140 KB Output is correct
5 Correct 9 ms 8140 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8140 KB Output is correct
2 Correct 9 ms 8140 KB Output is correct
3 Correct 9 ms 8152 KB Output is correct
4 Correct 11 ms 8140 KB Output is correct
5 Correct 9 ms 8140 KB Output is correct
6 Correct 9 ms 8024 KB Output is correct
7 Correct 10 ms 8140 KB Output is correct
8 Correct 10 ms 8148 KB Output is correct
9 Correct 9 ms 8140 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8140 KB Output is correct
2 Correct 9 ms 8140 KB Output is correct
3 Correct 9 ms 8152 KB Output is correct
4 Correct 11 ms 8140 KB Output is correct
5 Correct 9 ms 8140 KB Output is correct
6 Correct 9 ms 8024 KB Output is correct
7 Correct 10 ms 8140 KB Output is correct
8 Correct 10 ms 8148 KB Output is correct
9 Correct 9 ms 8140 KB Output is correct
10 Correct 12 ms 8268 KB Output is correct
11 Correct 11 ms 8268 KB Output is correct
12 Correct 10 ms 8252 KB Output is correct
13 Correct 10 ms 8268 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8140 KB Output is correct
2 Correct 9 ms 8140 KB Output is correct
3 Correct 9 ms 8152 KB Output is correct
4 Correct 11 ms 8140 KB Output is correct
5 Correct 9 ms 8140 KB Output is correct
6 Correct 9 ms 8024 KB Output is correct
7 Correct 10 ms 8140 KB Output is correct
8 Correct 10 ms 8148 KB Output is correct
9 Correct 9 ms 8140 KB Output is correct
10 Correct 12 ms 8268 KB Output is correct
11 Correct 11 ms 8268 KB Output is correct
12 Correct 10 ms 8252 KB Output is correct
13 Correct 10 ms 8268 KB Output is correct
14 Correct 125 ms 23720 KB Output is correct
15 Correct 74 ms 18984 KB Output is correct
16 Correct 118 ms 24700 KB Output is correct
17 Correct 69 ms 16320 KB Output is correct