oj.uz

Submission #1118276

# Submission time Handle Problem Language Result Execution time Memory
1118276 2024-11-25T07:40:30 Z Icelast Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 92 ms 40288 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 5*1e5+5, INF = 1e9+9, mod = 1e9+9, base = 101;
int N = 2e6;
vector<ll> bp(N+1, 1);
void calc(){
    for(int i = 1; i <= N; i++){
        bp[i] = bp[i-1]*base%mod;
    }
}
void solve(){
    string s;
    cin >> s;
    int n = s.size();
    s = ' ' + s;
    vector<ll> hsh(n+1, 0);
    for(int i = 1; i <= n; i++){
        hsh[i] = hsh[i-1]+(s[i]-'a'+1)*bp[i-1];
    }
    auto get_hash = [&](int l, int r) -> ll{
        ll raw = (hsh[r]-hsh[l-1]+mod)%mod;
        return raw*bp[N-l]%mod;
    };
    vector<int> f(n+1, -INF);
    f[0] = 0;
    int ans = 1;
    int L = 1, R = n;
    for(int i = 1; i <= n/2; i++){
        if(get_hash(L, i) == get_hash(n-i+1, R)){
            f[i] = f[L-1]+2;
            L = i+1;
            R = n-i+1-1;
        }
        if(i == n/2 && n%2==0){
            ans = max(ans, f[i]);
        }else{
            ans = max(ans, f[i]+1);
        }
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    calc();
    int t;
    cin >> t;
    while(t--){
        solve();
        cout << "\n";
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15964 KB Output is correct
2 Correct 15 ms 15964 KB Output is correct
3 Correct 15 ms 15964 KB Output is correct
4 Correct 13 ms 16148 KB Output is correct
5 Correct 15 ms 16112 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15964 KB Output is correct
2 Correct 15 ms 15964 KB Output is correct
3 Correct 15 ms 15964 KB Output is correct
4 Correct 13 ms 16148 KB Output is correct
5 Correct 15 ms 16112 KB Output is correct
6 Correct 14 ms 15952 KB Output is correct
7 Correct 15 ms 15952 KB Output is correct
8 Correct 13 ms 16076 KB Output is correct
9 Correct 15 ms 16128 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15964 KB Output is correct
2 Correct 15 ms 15964 KB Output is correct
3 Correct 15 ms 15964 KB Output is correct
4 Correct 13 ms 16148 KB Output is correct
5 Correct 15 ms 16112 KB Output is correct
6 Correct 14 ms 15952 KB Output is correct
7 Correct 15 ms 15952 KB Output is correct
8 Correct 13 ms 16076 KB Output is correct
9 Correct 15 ms 16128 KB Output is correct
10 Correct 14 ms 16364 KB Output is correct
11 Correct 13 ms 16220 KB Output is correct
12 Correct 15 ms 16396 KB Output is correct
13 Correct 13 ms 16116 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15964 KB Output is correct
2 Correct 15 ms 15964 KB Output is correct
3 Correct 15 ms 15964 KB Output is correct
4 Correct 13 ms 16148 KB Output is correct
5 Correct 15 ms 16112 KB Output is correct
6 Correct 14 ms 15952 KB Output is correct
7 Correct 15 ms 15952 KB Output is correct
8 Correct 13 ms 16076 KB Output is correct
9 Correct 15 ms 16128 KB Output is correct
10 Correct 14 ms 16364 KB Output is correct
11 Correct 13 ms 16220 KB Output is correct
12 Correct 15 ms 16396 KB Output is correct
13 Correct 13 ms 16116 KB Output is correct
14 Correct 92 ms 40288 KB Output is correct
15 Correct 65 ms 33744 KB Output is correct
16 Correct 88 ms 37536 KB Output is correct
17 Correct 59 ms 27864 KB Output is correct