oj.uz

Submission #966851

# Submission time Handle Problem Language Result Execution time Memory
966851 2024-04-20T13:25:22 Z OmarAlimammadzade Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 7 ms 5980 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
int p[N], h[N], P = 47, M = 1e9 + 7, n;
bool checkEqual(int a, int b, int l)
{
    int ha = (h[a + l - 1] - h[a - 1] + M) % M;
    int hb = (h[b + l - 1] - h[b - 1] + M) % M;
    return hb == 1ll * ha * p[b - a] % M;
}
int main()
{
    int t;
    cin >> t;
    p[0] = 1;
    for (int i = 1; i < N; i++)
        p[i] = 1ll * p[i - 1] * P % M;
    while (t--)
    {
        string s;
        cin >> s;
        int n = s.size();
        for (int i = 1; i <= n; i++)
            h[i] = (h[i - 1] + 1ll * (s[i - 1] - 'a' + 1) * p[i - 1] % M) % M;
        int l = 1, r = n, res = 0, k = 1;
        while (l <= r)
        {
            if (checkEqual(l, r - k + 1, k))
            {
                if (l + k < r)
                    res++;
                res++;
                l += k;
                r -= k;
                k = 1;
            }
            else
                k++;
        }
        cout << res << endl;
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5980 KB Output isn't correct
2 Halted 0 ms 0 KB -