oj.uz

Submission #972146

# Submission time Handle Problem Language Result Execution time Memory
972146 2024-04-30T07:26:50 Z efedmrlr Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 98 ms 22464 KB 
#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e6 + 5;
const lli INF = 1e17;
const int MOD = 1e9 + 7;
const int B = 3;
array<int, B> P = {31, 37, 73};
array<array<int, N>, B> pw;
int add(int x, int y) {
    if(x + y >= MOD) return x + y - MOD;
    return x + y; 
}
int subt(int x, int y) {
    if(x - y < 0) return x - y + MOD;
    return x - y;
}
int mult(int x, int y) {
    return (int)(1ll * x * y % MOD);
}
int fp(int x, int y) {
    int ret = 1;
    while(y > 0) {
        if(y & 1) {
            ret = mult(ret, x);
        }
        x = mult(x, x);
        y >>= 1;
    }
    return ret;
}
int n;
string s;
void solve() {
    cin >> s;
    n = (int)s.size();
    int ans = 0;
    array<int, B> fr, en;
    REP(b, B) {
        fr[b] = en[b] = 0;
    }
    int len = 0;
    int i = 0;
    for(; i < (n - 1) / 2 + 1; i++) {
        int j = n - i - 1;
        REP(b, B) {
            fr[b] = add(mult(fr[b], P[b]), s[i] - 'a' + 1);
            en[b] = add(en[b], mult(s[j] - 'a' + 1, pw[b][len])); 
        }
        len++;
        bool f = 1;
        REP(b, B) {
            if(fr[b] != en[b]) f = 0;
        }
        if(f) {
            ans += 2;
            if(i == j) ans--;
            len = 0;
            REP(b, B) {
                fr[b] = en[b] = 0;
            }
        }
    }
    if(len > 0) ans++;
    cout << ans << "\n";
}

signed main() {
    REP(b, B) {
        pw[b][0] = 1;
        for(int i = 1; i < N; i++) {
            pw[b][i] = mult(pw[b][i - 1], P[b]);
        }
    }
    fastio();
    int test = 1;
    cin >> test;
    while(test--) {
        solve();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12124 KB Output is correct
2 Correct 16 ms 12144 KB Output is correct
3 Correct 16 ms 12120 KB Output is correct
4 Correct 16 ms 12124 KB Output is correct
5 Correct 16 ms 12124 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12124 KB Output is correct
2 Correct 16 ms 12144 KB Output is correct
3 Correct 16 ms 12120 KB Output is correct
4 Correct 16 ms 12124 KB Output is correct
5 Correct 16 ms 12124 KB Output is correct
6 Correct 16 ms 12120 KB Output is correct
7 Correct 16 ms 12120 KB Output is correct
8 Correct 16 ms 12148 KB Output is correct
9 Correct 16 ms 12124 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12124 KB Output is correct
2 Correct 16 ms 12144 KB Output is correct
3 Correct 16 ms 12120 KB Output is correct
4 Correct 16 ms 12124 KB Output is correct
5 Correct 16 ms 12124 KB Output is correct
6 Correct 16 ms 12120 KB Output is correct
7 Correct 16 ms 12120 KB Output is correct
8 Correct 16 ms 12148 KB Output is correct
9 Correct 16 ms 12124 KB Output is correct
10 Correct 17 ms 12120 KB Output is correct
11 Correct 16 ms 12136 KB Output is correct
12 Correct 17 ms 12120 KB Output is correct
13 Correct 16 ms 12124 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12124 KB Output is correct
2 Correct 16 ms 12144 KB Output is correct
3 Correct 16 ms 12120 KB Output is correct
4 Correct 16 ms 12124 KB Output is correct
5 Correct 16 ms 12124 KB Output is correct
6 Correct 16 ms 12120 KB Output is correct
7 Correct 16 ms 12120 KB Output is correct
8 Correct 16 ms 12148 KB Output is correct
9 Correct 16 ms 12124 KB Output is correct
10 Correct 17 ms 12120 KB Output is correct
11 Correct 16 ms 12136 KB Output is correct
12 Correct 17 ms 12120 KB Output is correct
13 Correct 16 ms 12124 KB Output is correct
14 Correct 98 ms 19704 KB Output is correct
15 Correct 64 ms 18384 KB Output is correct
16 Correct 94 ms 22464 KB Output is correct
17 Correct 64 ms 18320 KB Output is correct