oj.uz

Submission #1103888

# Submission time Handle Problem Language Result Execution time Memory
1103888 2024-10-22T06:23:00 Z ezzzay Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 170 ms 12132 KB 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        string S;
        cin >> S;
        int N = S.size() / 2;
        long long cur1 = 0, cur2 = 0;
        long long a = 31, b = 1e9+7, mult = 1;
        int last = -1;
        int nb = 0;
        for (int i = 0; i < N; i++)
        {
            cur1 = (cur1 * a + S[i]) % b;
            cur2 = (cur2 + mult * S[S.size() - i - 1]) % b;
            mult = (mult * a) % b;
            if (cur1 == cur2)
            {
                last = i;
                cur1 = 0, cur2 = 0, mult = 1;
                nb += 2;
            }
        }
        if (S.size() % 2 || last < N - 1)
            nb++;
        cout << nb << '\n';
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 3 ms 336 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 3 ms 736 KB Output is correct
13 Correct 2 ms 336 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 3 ms 336 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 3 ms 736 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 170 ms 12132 KB Output is correct
15 Correct 92 ms 7332 KB Output is correct
16 Correct 153 ms 11456 KB Output is correct
17 Correct 85 ms 6848 KB Output is correct