oj.uz

Submission #915837

# Submission time Handle Problem Language Result Execution time Memory
915837 2024-01-24T18:52:08 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 304 ms 20120 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){
                ans++;
                break;
            }
        }
        cout << ans << '\n';
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 3 ms 2648 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 4 ms 2648 KB Output is correct
13 Correct 4 ms 2396 KB Output is correct
14 Correct 304 ms 20120 KB Output is correct
15 Correct 157 ms 15008 KB Output is correct
16 Correct 285 ms 19452 KB Output is correct
17 Correct 159 ms 13364 KB Output is correct