Submission #37019

#	Time	Username	Problem	Language	Result	Execution time	Memory
37019		DoanPhuDuc	Palindromic Partitions (CEOI17_palindromic)	C++98	100 / 100	113 ms	18616 KiB

palindromic

#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 1e6 + 10;
const int B = 1e5 + 7;

int n;

LL H[N], pw[N];

char S[N];

LL Hash(int l, int r) {
    return H[r] - H[l - 1] * pw[r - l + 1];
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    int TC; scanf("%d", &TC);
    pw[0] = 1;
    FOR(i, 1, 1000000) pw[i] = pw[i - 1] * B;
    while (TC--) {
        scanf("%s", S + 1); n = strlen(S + 1);
        FOR(i, 1, n) H[i] = H[i - 1] * B + (S[i] - 'a' + 1);
        int i = 1, p = n, ans = 0;
        FOD(j, n, 1) {
            if (S[i] == S[j]) {
                int L = p - j + 1;
                if (Hash(i, i + L - 1) == Hash(j, j + L - 1)) {
                    if (i + L - 1 >= j) {
                        ans++;
                        break;
                    } else {
                        ans += 2;
                        i = i + L;
                        p = j - 1;
                        if (i > p) break;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:33:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int TC; scanf("%d", &TC);
                             ^
palindromic.cpp:37:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", S + 1); n = strlen(S + 1);
                           ^

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40