#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1e6+5;
pii add(pii a, pii b) { return pii(a.x + b.x, a.y + b.y); }
pii sub(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); }
int t;
char A[N];
pii iden(23, 29), hpow[N], dp[N];
int main() {
hpow[0] = pii(1, 1);
for(int i = 1; i < N; i++) hpow[i] = mul(hpow[i-1], iden);
scanf("%d", &t);
while(t--) {
int ans = 0;
scanf(" %s", A+1);
hpow[0] = pii(0, 0);
int n = strlen(A+1);
for(int i = 1; i <= n; i++) dp[i] = add(mul(dp[i-1], iden), pii(A[i], A[i]));
int sz = 0;
for(int i = 1, j = n; i <= j; i++, j--) {
++sz;
int l = i-sz, r = j+sz-1;
pii lhs = sub(dp[i], mul(dp[l], hpow[sz]));
pii rhs = sub(dp[r], mul(dp[j-1], hpow[sz]));
if(lhs == rhs && i != j) ans += 2, sz = 0;
if(lhs == rhs && i == j) ++ans, sz = 0;
}
if(sz) ++ans;
printf("%d\n", ans);
}
return 0;
}
Compilation message
palindromic.cpp: In function 'int main()':
palindromic.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
~~~~~^~~~~~~~~~
palindromic.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", A+1);
~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
11 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
9 ms |
8192 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
11 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 7 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 8 |
Correct |
10 ms |
8176 KB |
Output is correct |
| 9 |
Correct |
8 ms |
8192 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
11 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 7 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 8 |
Correct |
10 ms |
8176 KB |
Output is correct |
| 9 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 10 |
Correct |
11 ms |
8320 KB |
Output is correct |
| 11 |
Correct |
10 ms |
8232 KB |
Output is correct |
| 12 |
Correct |
11 ms |
8320 KB |
Output is correct |
| 13 |
Correct |
11 ms |
8320 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
11 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 7 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 8 |
Correct |
10 ms |
8176 KB |
Output is correct |
| 9 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 10 |
Correct |
11 ms |
8320 KB |
Output is correct |
| 11 |
Correct |
10 ms |
8232 KB |
Output is correct |
| 12 |
Correct |
11 ms |
8320 KB |
Output is correct |
| 13 |
Correct |
11 ms |
8320 KB |
Output is correct |
| 14 |
Correct |
110 ms |
26888 KB |
Output is correct |
| 15 |
Correct |
70 ms |
22136 KB |
Output is correct |
| 16 |
Correct |
111 ms |
26280 KB |
Output is correct |
| 17 |
Correct |
59 ms |
17912 KB |
Output is correct |
