oj.uz

Submission #1045562

# Submission time Handle Problem Language Result Execution time Memory
1045562 2024-08-06T05:45:39 Z phoenix0423 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 121 ms 28048 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e6 + 5;
const int INF = 4e18;
const int N = 998244353;
const int A = 238435927;

void solve(){
    string s;
    cin>>s;
    int n = s.size();
    vector<int> h(n), p(n);
    h[0] = s[0], p[0] = 1;
    for(int i = 1; i < n; i++){
        p[i] = p[i - 1] * A % N;
        h[i] = (h[i - 1] * A + s[i]) % N;
    }
    int ans = 0;
    auto get = [&](int l, int r) -> int {
        return (h[r] - (l ? h[l - 1] * p[r - l + 1] % N : 0) + N) % N;
    }; 
    int l = 0;
    for(int i = 0; i < n; i++){
        int a = get(l, i), b = get(n - i - 1, n - l - 1);
        if(a == b){
            ans++;
            l = i + 1;
        }
    }
    cout<<ans<<"\n";
}

signed main(void){
    fastio;
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 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 0 ms 348 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 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 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 712 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 680 KB Output is correct
13 Correct 1 ms 668 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 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 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 712 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 680 KB Output is correct
13 Correct 1 ms 668 KB Output is correct
14 Correct 118 ms 28048 KB Output is correct
15 Correct 64 ms 22644 KB Output is correct
16 Correct 121 ms 26196 KB Output is correct
17 Correct 67 ms 15284 KB Output is correct