oj.uz

Submission #969458

# Submission time Handle Problem Language Result Execution time Memory
969458 2024-04-25T07:58:21 Z _callmelucian Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 112 ms 28736 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const ll base = 211;
const ll MOD = 1e9 + 21;
const int mn = 1e6 + 6;

ll pre[mn], basepow[mn];

ll getHash (int l, int r) {
    return (pre[r] - pre[l - 1] * basepow[r - l + 1] + MOD * MOD) % MOD;
}

void solve() {
    string s; cin >> s;
    int n = s.length();
    s = " " + s;

    for (int i = 1; i <= n; i++)
        pre[i] = (pre[i - 1] * base + s[i] - 'a' + 1) % MOD;

    int ans = 0;
    for (int r = n; n - r + 1 <= r;) {
        int l = n - r + 1, flg = 0;
        for (int k = 1; k < r - l + 1; k++) {
            if (getHash(l, l + k - 1) != getHash(r - k + 1, r)) continue;
            flg = 1, r -= k, ans += 2;
            break;
        }
        if (!flg) {
            ans++;
            break;
        }
    }
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    basepow[0] = 1;
    for (int i = 1; i < mn; i++)
        basepow[i] = basepow[i - 1] * base % MOD;

    int t; cin >> t;
    while (t--) solve();

    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8796 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 6 ms 8844 KB Output is correct
5 Correct 6 ms 8796 KB Output is correct
6 Correct 6 ms 8836 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 6 ms 8796 KB Output is correct
9 Correct 6 ms 8604 KB Output is correct
10 Correct 7 ms 8796 KB Output is correct
11 Correct 7 ms 8824 KB Output is correct
12 Correct 7 ms 8796 KB Output is correct
13 Correct 7 ms 8792 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8796 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 6 ms 8844 KB Output is correct
5 Correct 6 ms 8796 KB Output is correct
6 Correct 6 ms 8836 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 6 ms 8796 KB Output is correct
9 Correct 6 ms 8604 KB Output is correct
10 Correct 7 ms 8796 KB Output is correct
11 Correct 7 ms 8824 KB Output is correct
12 Correct 7 ms 8796 KB Output is correct
13 Correct 7 ms 8792 KB Output is correct
14 Correct 112 ms 28736 KB Output is correct
15 Correct 65 ms 23376 KB Output is correct
16 Correct 105 ms 27572 KB Output is correct
17 Correct 69 ms 19488 KB Output is correct