oj.uz

Submission #571660

# Submission time Handle Problem Language Result Execution time Memory
571660 2022-06-02T13:22:39 Z piOOE Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 58 ms 16736 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const int N = 1000001, mod = 998244353, X = 131;

int pw[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    pw[0] = 1;
    for (int i = 1; i < N; ++i)
        pw[i] = pw[i - 1] * (ll)X % mod;
    int test = 1;
    cin >> test;
    while (test--) {
        string s;
        cin >> s;
        int sumB = 0, sumE = 0, siz = 0;
        int n = sz(s);
        int ans = 0;
        for (int i = 0; i < n / 2; ++i) {
            ++siz;
            sumB = (sumB + pw[siz - 1] * (ll)s[i]) % mod;
            sumE = (sumE * (ll)X + s[n - i - 1]) % mod;
            if (sumB == sumE) {
                ans += 2;
                sumB = sumE = siz = 0;
            }
        }
        if (siz || n % 2 == 1)
            ++ans;
        cout << ans << '\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4180 KB Output is correct
2 Correct 7 ms 4240 KB Output is correct
3 Correct 7 ms 4180 KB Output is correct
4 Correct 7 ms 4180 KB Output is correct
5 Correct 8 ms 4216 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4180 KB Output is correct
2 Correct 7 ms 4240 KB Output is correct
3 Correct 7 ms 4180 KB Output is correct
4 Correct 7 ms 4180 KB Output is correct
5 Correct 8 ms 4216 KB Output is correct
6 Correct 7 ms 4244 KB Output is correct
7 Correct 7 ms 4180 KB Output is correct
8 Correct 7 ms 4240 KB Output is correct
9 Correct 7 ms 4180 KB Output is correct
10 Correct 8 ms 4288 KB Output is correct
11 Correct 8 ms 4308 KB Output is correct
12 Correct 7 ms 4308 KB Output is correct
13 Correct 8 ms 4252 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4180 KB Output is correct
2 Correct 7 ms 4240 KB Output is correct
3 Correct 7 ms 4180 KB Output is correct
4 Correct 7 ms 4180 KB Output is correct
5 Correct 8 ms 4216 KB Output is correct
6 Correct 7 ms 4244 KB Output is correct
7 Correct 7 ms 4180 KB Output is correct
8 Correct 7 ms 4240 KB Output is correct
9 Correct 7 ms 4180 KB Output is correct
10 Correct 8 ms 4288 KB Output is correct
11 Correct 8 ms 4308 KB Output is correct
12 Correct 7 ms 4308 KB Output is correct
13 Correct 8 ms 4252 KB Output is correct
14 Correct 51 ms 16736 KB Output is correct
15 Correct 32 ms 11620 KB Output is correct
16 Correct 58 ms 15724 KB Output is correct
17 Correct 37 ms 10740 KB Output is correct