Submission #235871

#	Time	Username	Problem	Language	Result	Execution time	Memory
235871		balbit	Palindromes (APIO14_palindrome)	C++14	23 / 100	1099 ms	82424 KiB

palindrome

#include <stdio.h>
#include <map>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define v 2
ll hhh[10005];
bool ispalindrome[10005][10005];
ll mod_inverse[10005];
char str[10005];
ll modpow(ll x,ll n)
{
	ll res=1;
	while(n)
	{
		if(n&1) res = res*x%mod;
		x = x*x%mod;
		n >>= 1;
	}
	return res;
}
ll calc(int l,int r)
{
	if(l==1) return hhh[r];
	ll d = (hhh[r]-hhh[l-1]+mod)%mod;
	return d*mod_inverse[l]%mod;
}
int main()
{
	scanf("%s",str);
	int n=strlen(str);
	for(int i=n;i>=1;i--) str[i] = str[i-1];
	for(int i=1;i<=n;i++) ispalindrome[i][i]=true;
	for(int i=1;i<n;i++) ispalindrome[i][i+1] = str[i]==str[i+1];
	for(int len=3;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			ispalindrome[i][i+len-1] = ispalindrome[i+1][i+len-2] & (str[i] == str[i+len-1]);
		}
	}
	ll cur = 1LL;
	for(int i=1;i<=10005;i++)
	{
		mod_inverse[i] = modpow(cur,mod-2); cur=cur*v%mod;
	}
	cur = 1LL;
	for(int i=1;i<=n;i++)
	{
		hhh[i] = (hhh[i-1]+cur*(str[i]-'a')%mod)%mod;
		cur = cur*v%mod;
	}
	int res=0;
	for(int i=1;i<=n;i++)
	{
		map<ll,int>ch; int maxvalue=0;
		for(int j=1;j+i-1<=n;j++)
		{
			if(ispalindrome[j][j+i-1]) maxvalue = max(maxvalue,++ch[calc(j,j+i-1)]);
		}
		res = max(res,maxvalue*i);
	}
	printf("%d%c",res,10);
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",str);
  ~~~~~^~~~~~~~~~
palindrome.cpp:48:18: warning: iteration 10004 invokes undefined behavior [-Waggressive-loop-optimizations]
   mod_inverse[i] = modpow(cur,mod-2); cur=cur*v%mod;
   ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
palindrome.cpp:46:15: note: within this loop
  for(int i=1;i<=10005;i++)
              ~^~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27