oj.uz

Submission #915865

# Submission time Handle Problem Language Result Execution time Memory
915865 2024-01-24T19:52:58 Z cper Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 1 ms 2392 KB 
# include <bits/stdc++.h>

typedef std::string st;
typedef long long ll;

using namespace std;

ll p[1000006], h[1000006];
ll a, n, l, c, i;
ll h1, h2;

st t;

bool f;

bool check_equal(ll a, ll b, ll l) {
    h1 = (h[a + l - 1] - h[a - 1]) * p[b - a];
    h2 = (h[b + l - 1] - h[b - 1]);

    return h1 == h2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a;

    while (a --) {
        cin >> t;

        n = t.size();

        p[0] = 1, p[1] = 47;

        for (i = 2; i < n; i ++) {
            p[i] = p[i - 1] * p[1];
        }

        h[0] = 0;

        for (i = 1; i <= n; i ++) {
            h[i] = h[i - 1] + (t[i - 1] - 'a' + 1) * p[i - 1];
        }

        l = 1, c = 1;

        while (l <= n / 2) {
            i = 1, f = false;

            for (; i <= n / 2 - l + 1; i ++) {
                // cout << t.substr(l-1, i) << ' ' << t.substr(n - l - i + 1, i) << '\n';

                if (check_equal(l, n - l - i + 2, i)) {
                    // cout << "fuck you\n";
                    c += 2;
                    l = l + i;
                    f = true;
                    break;
                }
            }

            if (!f) {
                break;
            }
        }

        cout << c << '\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 -