oj.uz

Submission #242039

# Submission time Handle Problem Language Result Execution time Memory
242039 2020-06-26T15:55:27 Z parsa_mobed Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 103 ms 20584 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10, B1 = 619, B2 = 787;
int H1[N], H2[N], pw1[N], pw2[N];

pair <int , int> HASH(int l, int r)
{
    return {H1[r] - H1[l - 1] * pw1[r - l + 1] , H2[r] - H2[l - 1] * pw2[r - l + 1]};
}

void Main()
{
    memset(H1, 0, sizeof H1);
    memset(H2, 0, sizeof H2);
    string s; cin >> s;
    int n = s.size();
    for (int i = 1; i <= n; i ++) {
        H1[i] = H1[i - 1] * B1 + (s[i - 1] - 'a' + 17);
        H2[i] = H2[i - 1] * B2 + (s[i - 1] - 'a' + 33);
    }
    int ans = 0;
    int l = 1;
    for (int i = 1; i <= n / 2; i ++) {
        if (HASH(l, i) == HASH(n - i + 1, n - l + 1)) {
            ans+=2;
            l = i + 1;
        }
    }
    cout << ans + ((l - 1) * 2 < n) << "\n";
    return ;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    pw1[0] = pw2[0] = 1;
    for (int i = 1; i < N; i ++) pw1[i] = pw1[i - 1] * B1, pw2[i] = pw2[i - 1] * B2;
    int t; cin >> t;
    while (t--) {
        Main();
    }
}
/*
testcase
4
bonobo
deleted
racecar
racecars
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 16000 KB Output is correct
2 Correct 21 ms 16000 KB Output is correct
3 Correct 16 ms 16000 KB Output is correct
4 Correct 21 ms 16000 KB Output is correct
5 Correct 20 ms 16000 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 16000 KB Output is correct
2 Correct 21 ms 16000 KB Output is correct
3 Correct 16 ms 16000 KB Output is correct
4 Correct 21 ms 16000 KB Output is correct
5 Correct 20 ms 16000 KB Output is correct
6 Correct 19 ms 16000 KB Output is correct
7 Correct 18 ms 16000 KB Output is correct
8 Correct 19 ms 16000 KB Output is correct
9 Correct 19 ms 16000 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 16000 KB Output is correct
2 Correct 21 ms 16000 KB Output is correct
3 Correct 16 ms 16000 KB Output is correct
4 Correct 21 ms 16000 KB Output is correct
5 Correct 20 ms 16000 KB Output is correct
6 Correct 19 ms 16000 KB Output is correct
7 Correct 18 ms 16000 KB Output is correct
8 Correct 19 ms 16000 KB Output is correct
9 Correct 19 ms 16000 KB Output is correct
10 Correct 20 ms 16128 KB Output is correct
11 Correct 19 ms 16052 KB Output is correct
12 Correct 20 ms 16128 KB Output is correct
13 Correct 19 ms 16128 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 16000 KB Output is correct
2 Correct 21 ms 16000 KB Output is correct
3 Correct 16 ms 16000 KB Output is correct
4 Correct 21 ms 16000 KB Output is correct
5 Correct 20 ms 16000 KB Output is correct
6 Correct 19 ms 16000 KB Output is correct
7 Correct 18 ms 16000 KB Output is correct
8 Correct 19 ms 16000 KB Output is correct
9 Correct 19 ms 16000 KB Output is correct
10 Correct 20 ms 16128 KB Output is correct
11 Correct 19 ms 16052 KB Output is correct
12 Correct 20 ms 16128 KB Output is correct
13 Correct 19 ms 16128 KB Output is correct
14 Correct 103 ms 20528 KB Output is correct
15 Correct 64 ms 20464 KB Output is correct
16 Correct 96 ms 20584 KB Output is correct
17 Correct 68 ms 19256 KB Output is correct