oj.uz

Submission #1114907

# Submission time Handle Problem Language Result Execution time Memory
1114907 2024-11-19T18:11:33 Z vladilius Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 328 ms 27812 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int base = 31;

int f(char x){
    return x - 'a' + 1;
}

struct hash_str{
    vector<ll> pm, hm;
    void init(string s){
        int n = (int) s.length();
        pm.resize(n + 1);
        pm[0] = 1;
        for (int i = 1; i <= n; i++){
            pm[i] = (pm[i - 1] * base) % mod;
        }
        hm.resize(n + 1);
        hm[0] = 0;
        for (int i = 1; i <= n; i++){
            hm[i] = (hm[i - 1] * base + f(s[i - 1])) % mod;
        }
    }
    ll get(int l, int r){
        return ((hm[r] - hm[l - 1] * pm[r - l + 1]) % mod + mod) % mod;
    }
};

int main(){
    int t; cin>>t;
    while (t--){
        string s; cin>>s;
        hash_str sol; sol.init(s);
        int i = 1, j = 1, n = (int) s.length(), cnt = 0;;
        while (2 * j <= n){
            if (sol.get(i, j) == sol.get(n - j + 1, n - i + 1)){
                i = j + 1;
                cnt++;
            }
            j++;
        }
        cout<<2 * cnt + (i <= n - i + 1)<<"\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 440 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 440 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 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 440 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 4 ms 688 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 6 ms 700 KB Output is correct
13 Correct 4 ms 660 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 440 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 4 ms 688 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 6 ms 700 KB Output is correct
13 Correct 4 ms 660 KB Output is correct
14 Correct 328 ms 27812 KB Output is correct
15 Correct 170 ms 23000 KB Output is correct
16 Correct 314 ms 26104 KB Output is correct
17 Correct 189 ms 15232 KB Output is correct