Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
29868893 Practice:
pkien
835D - 38 GNU C++ Time limit exceeded on test 5 3000 ms 144 KB 2017-08-29 17:57:31 2017-08-29 17:57:31
 
 
→ Source
/*input
abba
*/

#include <bits/stdc++.h> 
#define N 5005
using namespace std;

const long long mod = (long long)1e9 + 7, base = 139;
int n;
char s[N];
long long pw[N], prefhsh[N], suffhsh[N];

long long rangehsh(int l, int r) {
	return ((prefhsh[r] - prefhsh[l - 1] * pw[r - l + 1]) % mod + mod) % mod;
}
long long rangehshr(int l, int r) {
	//l = n - l + 1; r = n - r + 1;
	swap(l, r);
	return ((suffhsh[r] - suffhsh[l + 1] * pw[l- r + 1]) % mod + mod) % mod;
}
bool ispalin(int l, int r) {
	return rangehsh(l, r) == rangehshr(l, r);
}
int kpalin(int l, int r) {
	if (l == r) return 1;
	if (l + 1 == r) return s[l] == s[r] ? 2 : 0;
	int half = (r - l + 1) >> 1;
	int mid1 = l + half - 1, mid2 = r - half + 1;
	int res = kpalin(l, mid1);
	if (!res) return ispalin(l, r);
	if (rangehsh(l, mid1) == rangehsh(mid2, r)) return res + 1;
	return ispalin(l, r);
}
int ans[N];
int main() {
	scanf("%s", s + 1); while (s[n + 1]) n++;
	pw[0] = 1;
	for (int i = 1; i <= n; i++) {
		pw[i] = pw[i - 1] * base % mod;
		prefhsh[i] = (prefhsh[i - 1] * base + s[i] - 'a') % mod;;	
	}
	for (int i = n; i >= 1; i--) suffhsh[i] = (suffhsh[i + 1] * base + s[i] - 'a') % mod;
	for (int i = 1; i <= n; i++) 
		for (int j = i; j <= n; j++) ans[0]++, ans[kpalin(i, j) + 1]--;
	for (int i = 1; i <= n; i++) printf("%d ", ans[i] += ans[i - 1]);
	putchar('\n');
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details