oj.uz

Submission #915836

# Submission time Handle Problem Language Result Execution time Memory
915836 2024-01-24T18:50:18 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
 1 ms 2392 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 1e6 + 5;
const int P = 43;
const int M = 1e9 + 7;

int n;
int p[N], h[N];

bool check_equal(int a, int b, int l) {
    int ha = (h[a + l - 1] - h[a - 1] + M) % M;
    int hb = (h[b + l - 1] - h[b - 1] + M) % M;
    return 1ll * ha * p[b - a] % M == hb;
}

int main() {
    int Q; cin >> Q;
    while(Q--){
        string s;
        cin >> s;
        n = s.size();

        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            p[i] = 1ll * p[i - 1] * P % M;
        }

        h[0] = 0;
        for (int i = 1; i <= n; i++) {
            h[i] = (h[i - 1] + 1LL * (s[i - 1] - 'a' + 1) * p[i - 1] % M) % M;
        }
        int p1 = 0, p2 = n - 1;
        ll ans = 0;
        while(p1 < p2){
            bool ok = false;
            for(int k = 1; 2 * k <= p2 - p1 + 1; k++){
                if(check_equal(p1 + 1, p2 - k + 2, k)){
                    p1 += k;
                    p2 -= k;
                    ans += 2;
                    ok = true;
                    break;
                }
            }
            if(!ok) break;
        }
        cout << ans + 1 << '\n';
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -