oj.uz

Submission #115223

# Submission time Handle Problem Language Result Execution time Memory
115223 2019-06-06T06:55:37 Z minhtung0404 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 134 ms 21024 KB 
//https://oj.uz/problem/view/CEOI17_palindromic

#include<bits/stdc++.h>
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
using namespace std;

int t, h[N], po[N];
string s;

int get(int l, int r){
    return (h[r] - 1LL * h[l-1] * po[r-l+1] + 1LL * mod * mod) % mod;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    po[0] = 1;
    for (int i = 1; i < N; i++) po[i] = 53LL * po[i-1] % mod;
    cin >> t;
    while (t--){
        cin >> s;
        int n = s.size(); s = '.' + s;
        for (int i = 1; i <= n; i++) h[i] = (53LL * h[i-1] + s[i] - 'a') % mod;
        int l = 1, r = n, ans = 0;
        while (l <= r){
            bool ck = false;
            for (int i = l; i < r; i++){
                if (get(l, i) == get(n+1-i, r)){
                    l = i+1, r = n-i;
                    ans += 2;
                    ck = true;
                    break;
                }
            }
            if (!ck) {
                ans++;
                break;
            }
        }
        cout << ans << "\n";
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4224 KB Output is correct
2 Correct 10 ms 4224 KB Output is correct
3 Correct 10 ms 4224 KB Output is correct
4 Correct 10 ms 4224 KB Output is correct
5 Correct 10 ms 4224 KB Output is correct
6 Correct 10 ms 4224 KB Output is correct
7 Correct 10 ms 4224 KB Output is correct
8 Correct 10 ms 4224 KB Output is correct
9 Correct 10 ms 4224 KB Output is correct
10 Correct 11 ms 4480 KB Output is correct
11 Correct 11 ms 4352 KB Output is correct
12 Correct 11 ms 4480 KB Output is correct
13 Correct 11 ms 4352 KB Output is correct
14 Correct 134 ms 19932 KB Output is correct
15 Correct 82 ms 15164 KB Output is correct
16 Correct 130 ms 21024 KB Output is correct
17 Correct 76 ms 12412 KB Output is correct