Submission #63157

#	Time	Username	Problem	Language	Result	Execution time	Memory
63157		khsoo01	Palindromic Partitions (CEOI17_palindromic)	C++11	100 / 100	213 ms	41780 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1000005, M1 = 1e9+7, M2 = 69746969;

ll n, p1[N] = {1}, p2[N] = {1};
char a[N];

struct Hash {
	ll v1, v2, l;
	Hash () {cl();}
	void cl () {v1 = 0; v2 = 0; l = 0;}
};

Hash operator + (char B, Hash A) {
	Hash ret;
	ret.v1 = (A.v1 + B * p1[A.l]) % M1;
	ret.v2 = (A.v2 + B * p2[A.l]) % M2;
	ret.l = A.l + 1;
	return ret;
}

Hash operator + (Hash A, char B) {
	Hash ret;
	ret.v1 = (A.v1 * 26 + B) % M1;
	ret.v2 = (A.v2 * 26 + B) % M2;
	ret.l = A.l + 1;
	return ret;
}

bool operator == (Hash A, Hash B) {
	return (A.l == B.l && A.v1 == B.v1 && A.v2 == B.v2);
}

void solve () {
	scanf("%s",a+1);
	n = strlen(a+1);
	for(ll i=1;i<=n;i++) {
		p1[i] = p1[i-1] * 26 % M1;
		p2[i] = p2[i-1] * 26 % M2;
		a[i] -= 'a';
	}
	Hash A, B;
	ll ans = 0;
	for(ll i=1;i<=n/2;i++) {
		A = A + a[i];
		B = a[n-i+1] + B;
		if(A == B) {A.cl(); B.cl(); ans += 2;}
	}
	if(n%2 || A.l) ans++;
	printf("%lld\n",ans);
}

int main()
{
	int tc;
	scanf("%d",&tc);
	while(tc--) solve();
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",a+1);
  ~~~~~^~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&tc);
  ~~~~~^~~~~~~~~~

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