oj.uz

Submission #884700

# Submission time Handle Problem Language Result Execution time Memory
884700 2023-12-08T06:31:28 Z theghostking Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 179 ms 30552 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int P = 31;
const int M = 1e9+9;
 
vector<int> binpow;
vector<int> pref;
 
int gethash(int l, int r){
    int h = ((pref[r+1] - (binpow[r-l+1] * pref[l]))%M + M)%M;
    return h;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--){
        string s;
        cin >> s;
        int n = s.size();
        binpow.clear();
        binpow.resize(n);
        binpow[0] = 1;
        for (int i = 1; i<n; i++){
            binpow[i] = (binpow[i-1]*P) % M;
        }
        pref.clear();
        pref.resize(n+1);
        pref[0] = 0;
        for (int i = 1; i<=n; i++){
            pref[i] = ((pref[i-1]*P)+(s[i-1]-'a'+1)) % M;
        }
        int r = 0;
        int ln = 0;
        int ans = 0;
        vector<bool> vis(n);
        int lst = n-1;
        while (r+ln < n/2){
            int st = r; int stt = r+ln;
            int nd = lst-ln; int ndd = lst;
            int one = gethash(st,stt);
            int two = gethash(nd,ndd);
            //cout << st << " " << stt << "  " << nd << " " << ndd << "\n";
            //cout << one << " " << two << "\n\n";
            if (one == two){
                for (int i = st; i<=stt; i++){
                    vis[i] = true;
                }
                for (int i = nd; i<=ndd; i++){
                    vis[i] = true;
                }
                ans += 2;
                r += ln+1;
                lst -= ln+1;
                ln = 0;
            }
            else{
                ln++;
            }
        }
        int bk = 0;
        for (int i = 0; i<n; i++){
            bk += vis[i];
        }
        if (bk != n) ans++;
        cout << ans << '\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 2 ms 856 KB Output is correct
13 Correct 2 ms 468 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 2 ms 856 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 179 ms 28728 KB Output is correct
15 Correct 100 ms 30552 KB Output is correct
16 Correct 178 ms 29252 KB Output is correct
17 Correct 92 ms 15800 KB Output is correct