oj.uz

Submission #486790

# Submission time Handle Problem Language Result Execution time Memory
486790 2021-11-12T20:25:38 Z mahdavifar Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 237 ms 20092 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000005;

const long long m    = 1000000007;
const long long p    = 999999893;
long long power[maxn] = {};

int main()
{
    // preprocess
    power[0] = 1;
    for (int i = 1; i < maxn; i++)
        power[i] = (power[i-1] * p) % m;

    // get number of test cases
    int T; cin >> T;

    // solve test cases
    for (int t = 0; t < T; t++)
    {
        string s; cin >> s;
        int n = s.length();

        int base = 0, ans = 0;
        long long hash1 = 0, hash2 = 0;

        for( int i=0, j=n-1; i < n-i; i++, j--)
        {
            hash1 = (hash1 + s[i] * power[i]) % m;
            hash2 = (hash2 + s[j] * power[j]) % m;

            if ((hash1 * power[j-base]) % m == hash2) {
                ans += 2 - (i == j);

                hash1 = hash2 = 0;
                base = i + 1;
            }
        }

        if (hash1 != 0)
            ans += 1;

        cout << ans << endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8012 KB Output is correct
2 Correct 9 ms 8060 KB Output is correct
3 Correct 10 ms 8116 KB Output is correct
4 Correct 8 ms 8012 KB Output is correct
5 Correct 8 ms 8012 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8012 KB Output is correct
2 Correct 9 ms 8060 KB Output is correct
3 Correct 10 ms 8116 KB Output is correct
4 Correct 8 ms 8012 KB Output is correct
5 Correct 8 ms 8012 KB Output is correct
6 Correct 8 ms 8012 KB Output is correct
7 Correct 9 ms 8120 KB Output is correct
8 Correct 8 ms 8012 KB Output is correct
9 Correct 8 ms 8012 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8012 KB Output is correct
2 Correct 9 ms 8060 KB Output is correct
3 Correct 10 ms 8116 KB Output is correct
4 Correct 8 ms 8012 KB Output is correct
5 Correct 8 ms 8012 KB Output is correct
6 Correct 8 ms 8012 KB Output is correct
7 Correct 9 ms 8120 KB Output is correct
8 Correct 8 ms 8012 KB Output is correct
9 Correct 8 ms 8012 KB Output is correct
10 Correct 10 ms 8140 KB Output is correct
11 Correct 9 ms 8140 KB Output is correct
12 Correct 10 ms 8132 KB Output is correct
13 Correct 10 ms 8128 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8012 KB Output is correct
2 Correct 9 ms 8060 KB Output is correct
3 Correct 10 ms 8116 KB Output is correct
4 Correct 8 ms 8012 KB Output is correct
5 Correct 8 ms 8012 KB Output is correct
6 Correct 8 ms 8012 KB Output is correct
7 Correct 9 ms 8120 KB Output is correct
8 Correct 8 ms 8012 KB Output is correct
9 Correct 8 ms 8012 KB Output is correct
10 Correct 10 ms 8140 KB Output is correct
11 Correct 9 ms 8140 KB Output is correct
12 Correct 10 ms 8132 KB Output is correct
13 Correct 10 ms 8128 KB Output is correct
14 Correct 237 ms 20092 KB Output is correct
15 Correct 132 ms 15156 KB Output is correct
16 Correct 216 ms 19232 KB Output is correct
17 Correct 123 ms 14612 KB Output is correct