oj.uz

Submission #666758

# Submission time Handle Problem Language Result Execution time Memory
666758 2022-11-29T15:03:27 Z ParsaS Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 137 ms 24796 KB 
// In the name  f God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1e6 + 5, MOD = 1e9 + 7, P = 101;
int n, pw[N], hsh[N], inv[N];
string s;

int get_hsh(int l, int r) {
    //cout << hsh[r] << ' ' << hsh[l - 1] << endl;
    return 1LL * (hsh[r] - hsh[l - 1] + MOD) % MOD * inv[l - 1] % MOD;
}
int binpow(int a, int b) {
    return b ? 1LL * binpow(1LL * a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD : 1;
}
void solve() {
    cin >> s;
    n = s.size();
    s = '.' + s;
    for (int i = 1; i <= n; i++) {
        hsh[i] = (hsh[i - 1] + 1LL * (s[i] - 'a' + 1) * pw[i] % MOD) % MOD;
    }
    int l = 1, r = n, ans = 0;
    while (l <= r) {
        int lp = l, rp = r;
        while (l <= r && get_hsh(lp, l) != get_hsh(r, rp))
            l++, r--;
        if (l >= r) {
            ans++;
            break;
        }
        ans += 2;
        l++, r--;
    }
    cout << ans << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    pw[0] = 1;
    for (int i = 1; i < N; i++)
        pw[i] = 1LL * P * pw[i - 1] % MOD;
    inv[N - 1] = binpow(pw[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--)
        inv[i] = 1LL * inv[i + 1] * P % MOD;
    int tc = 1; cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8148 KB Output is correct
2 Correct 15 ms 8148 KB Output is correct
3 Correct 15 ms 8156 KB Output is correct
4 Correct 15 ms 8148 KB Output is correct
5 Correct 15 ms 8152 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8148 KB Output is correct
2 Correct 15 ms 8148 KB Output is correct
3 Correct 15 ms 8156 KB Output is correct
4 Correct 15 ms 8148 KB Output is correct
5 Correct 15 ms 8152 KB Output is correct
6 Correct 15 ms 8148 KB Output is correct
7 Correct 15 ms 8148 KB Output is correct
8 Correct 15 ms 8076 KB Output is correct
9 Correct 16 ms 8172 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8148 KB Output is correct
2 Correct 15 ms 8148 KB Output is correct
3 Correct 15 ms 8156 KB Output is correct
4 Correct 15 ms 8148 KB Output is correct
5 Correct 15 ms 8152 KB Output is correct
6 Correct 15 ms 8148 KB Output is correct
7 Correct 15 ms 8148 KB Output is correct
8 Correct 15 ms 8076 KB Output is correct
9 Correct 16 ms 8172 KB Output is correct
10 Correct 16 ms 8244 KB Output is correct
11 Correct 16 ms 8232 KB Output is correct
12 Correct 16 ms 8252 KB Output is correct
13 Correct 17 ms 8160 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8148 KB Output is correct
2 Correct 15 ms 8148 KB Output is correct
3 Correct 15 ms 8156 KB Output is correct
4 Correct 15 ms 8148 KB Output is correct
5 Correct 15 ms 8152 KB Output is correct
6 Correct 15 ms 8148 KB Output is correct
7 Correct 15 ms 8148 KB Output is correct
8 Correct 15 ms 8076 KB Output is correct
9 Correct 16 ms 8172 KB Output is correct
10 Correct 16 ms 8244 KB Output is correct
11 Correct 16 ms 8232 KB Output is correct
12 Correct 16 ms 8252 KB Output is correct
13 Correct 17 ms 8160 KB Output is correct
14 Correct 137 ms 23664 KB Output is correct
15 Correct 81 ms 19024 KB Output is correct
16 Correct 128 ms 24796 KB Output is correct
17 Correct 79 ms 16316 KB Output is correct