oj.uz

Submission #867701

# Submission time Handle Problem Language Result Execution time Memory
867701 2023-10-29T09:02:46 Z Dec0Dedd Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 98 ms 36436 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1e9+7;
const ll P = 2137;
const int N = 1e6+10;

ll p[N], h[N], inv[N];

ll bpw(ll x, ll n) {
    if (n == 0) return 1;
    ll c=bpw(x, n/2);
    (c=c*c)%=MOD;
    if (n&1) return (c*x)%MOD;
    return c;
}

ll hsh(int l, int r) {
    ll v=((h[r]-h[l-1])%MOD+MOD)%MOD;
    return (v*inv[l])%MOD;
}

void solve() {
    string s; cin>>s; h[0]=0;

    int n=s.size();
    for (int i=1; i<=n; ++i) h[i]=(h[i-1]+s[i-1]*p[i])%MOD;

    int ans=0, l=0;
    for (int i=1; i<=n/2; ++i) {
        if (hsh(l+1, i) == hsh(n-i+1, n-l)) l=i, ans+=2;
    }

    if (l < (n+1)/2) ++ans;
    cout<<ans<<"\n";
}

int main() {
    ios_base::sync_with_stdio(NULL);
    cout.tie(NULL);
    
    p[0]=1, p[1]=P;
    inv[0]=1, inv[1]=bpw(P, MOD-2);
    for (int i=2; i<N; ++i) (p[i]=p[i-1]*P)%=MOD, (inv[i]=inv[i-1]*inv[1])%=MOD;

    int t; cin>>t;
    while (t--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17752 KB Output is correct
2 Correct 7 ms 17756 KB Output is correct
3 Correct 7 ms 17764 KB Output is correct
4 Correct 7 ms 17756 KB Output is correct
5 Correct 7 ms 17756 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17752 KB Output is correct
2 Correct 7 ms 17756 KB Output is correct
3 Correct 7 ms 17764 KB Output is correct
4 Correct 7 ms 17756 KB Output is correct
5 Correct 7 ms 17756 KB Output is correct
6 Correct 7 ms 17756 KB Output is correct
7 Correct 7 ms 17752 KB Output is correct
8 Correct 7 ms 17756 KB Output is correct
9 Correct 7 ms 17752 KB Output is correct
10 Correct 8 ms 17756 KB Output is correct
11 Correct 7 ms 17756 KB Output is correct
12 Correct 7 ms 17756 KB Output is correct
13 Correct 7 ms 17756 KB Output is correct
14 Correct 98 ms 36436 KB Output is correct
15 Correct 55 ms 31348 KB Output is correct
16 Correct 95 ms 35272 KB Output is correct
17 Correct 65 ms 28524 KB Output is correct