Submission #56773

#	Time	Username	Problem	Language	Result	Execution time	Memory
56773		win11905	Palindromic Partitions (CEOI17_palindromic)	C++11	100 / 100	92 ms	38824 KiB

palindromic

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int N = 1e6+5;

char A[N];
pii d[N], iden(131, 133);

pii add(pii a, pii b) { return pii(a.x + b.x, a.y + b.y); }
pii mul(pii a, pii b) { return pii(a.x * b.x, a.y * b.y); }

void solve() {
    scanf("%s", A);
    int n = strlen(A), cnt = 0;
    pii lhs, rhs;
    for(int i = 0, p = 0; i < n; ++i, ++p) {
        lhs = add(pii(A[i], A[i]), mul(iden, lhs));
        rhs = add(rhs, mul(pii(A[n-i-1], A[n-i-1]), d[p]));
        if(lhs == rhs) cnt++, p = -1, lhs = rhs = pii(0, 0);
    }
    printf("%d\n", cnt);
}

int main() {
    d[0] = pii(1, 1);
    for(int i = 1; i < N; ++i) d[i] = mul(d[i-1], iden);
    int T; scanf("%d", &T);
    while(T--) solve();
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", A);
     ~~~~~^~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:30:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int T; scanf("%d", &T);
            ~~~~~^~~~~~~~~~

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