oj.uz

Submission #481991

# Submission time Handle Problem Language Result Execution time Memory
481991 2021-10-22T14:43:55 Z izhang05 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 146 ms 26784 KB 
#include <bits/stdc++.h>

using namespace std;

//#define DEBUG
void setIO(const string &name) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin.exceptions(istream::failbit);
#ifdef LOCAL
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
    freopen((name + ".out").c_str(), "w", stderr);
#endif
}

const int maxn = 1e6 + 5;
const long long m1 = 1e9 + 9, p = 9973;

long long pw[maxn]; // Stores the powers of p modulo m1
int n;
string s;
long long hsh[maxn];

void calc_hashes() {
    hsh[0] = 1;
    for (int i = 0; i < n; ++i) {
        hsh[i + 1] = ((hsh[i] * p) % m1 + s[i]) % m1;
    }
}

long long get_hash(int a, int b) { // [a, b]
    return (hsh[b + 1] - (hsh[a] * pw[b - a + 1]) % m1 + m1) % m1;
}

void calc_pow() {
    pw[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        pw[i] = (pw[i - 1] * p) % m1;
    }
}

int main() {
    setIO("1");

    int t;
    cin >> t;
    calc_pow();
    while (t--) {
        cin >> s;
        n = int(s.size());
        calc_hashes();
        int sol = 1;
        for (int i = 0; i < n / 2; ++i) {
            int j = i, l = n - i - 1, r = n - i - 1;
            for (; j < n / 2; ++j, --l) {
                if (get_hash(i, j) == get_hash(l, r)) {
                    sol += 2;
                    if (n % 2 == 0 && j == n / 2 - 1) {
                        --sol;
                    }
                    break;
                }
            }
            i = j;
        }
        cout << sol << "\n";
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8140 KB Output is correct
2 Correct 8 ms 8108 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 10 ms 8136 KB Output is correct
5 Correct 8 ms 8104 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8140 KB Output is correct
2 Correct 8 ms 8108 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 10 ms 8136 KB Output is correct
5 Correct 8 ms 8104 KB Output is correct
6 Correct 8 ms 8140 KB Output is correct
7 Correct 10 ms 8140 KB Output is correct
8 Correct 12 ms 8140 KB Output is correct
9 Correct 10 ms 8140 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8140 KB Output is correct
2 Correct 8 ms 8108 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 10 ms 8136 KB Output is correct
5 Correct 8 ms 8104 KB Output is correct
6 Correct 8 ms 8140 KB Output is correct
7 Correct 10 ms 8140 KB Output is correct
8 Correct 12 ms 8140 KB Output is correct
9 Correct 10 ms 8140 KB Output is correct
10 Correct 9 ms 8344 KB Output is correct
11 Correct 9 ms 8216 KB Output is correct
12 Correct 9 ms 8268 KB Output is correct
13 Correct 9 ms 8316 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8140 KB Output is correct
2 Correct 8 ms 8108 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 10 ms 8136 KB Output is correct
5 Correct 8 ms 8104 KB Output is correct
6 Correct 8 ms 8140 KB Output is correct
7 Correct 10 ms 8140 KB Output is correct
8 Correct 12 ms 8140 KB Output is correct
9 Correct 10 ms 8140 KB Output is correct
10 Correct 9 ms 8344 KB Output is correct
11 Correct 9 ms 8216 KB Output is correct
12 Correct 9 ms 8268 KB Output is correct
13 Correct 9 ms 8316 KB Output is correct
14 Correct 146 ms 26784 KB Output is correct
15 Correct 80 ms 22140 KB Output is correct
16 Correct 128 ms 26152 KB Output is correct
17 Correct 77 ms 18016 KB Output is correct