Submission #235870

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
235870	2020-05-30T08:33:45 Z	balbit	Palindromes (APIO14_palindrome)	C++14	Compilation error	0 ms	0 KB

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 hash[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 hash[r];
	ll d = (hash[r]-hash[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++)
	{
		hash[i] = (hash[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

palindrome.cpp: In function 'll calc(int, int)':
palindrome.cpp:27:18: error: reference to 'hash' is ambiguous
  if(l==1) return hash[r];
                  ^~~~
palindrome.cpp:10:4: note: candidates are: ll hash [10005]
 ll hash[10005];
    ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/stdexcept:39,
                 from /usr/include/c++/7/array:39,
                 from /usr/include/c++/7/tuple:39,
                 from /usr/include/c++/7/bits/stl_map.h:63,
                 from /usr/include/c++/7/map:61,
                 from palindrome.cpp:2:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp:28:10: error: reference to 'hash' is ambiguous
  ll d = (hash[r]-hash[l-1]+mod)%mod;
          ^~~~
palindrome.cpp:10:4: note: candidates are: ll hash [10005]
 ll hash[10005];
    ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/stdexcept:39,
                 from /usr/include/c++/7/array:39,
                 from /usr/include/c++/7/tuple:39,
                 from /usr/include/c++/7/bits/stl_map.h:63,
                 from /usr/include/c++/7/map:61,
                 from palindrome.cpp:2:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp:28:18: error: reference to 'hash' is ambiguous
  ll d = (hash[r]-hash[l-1]+mod)%mod;
                  ^~~~
palindrome.cpp:10:4: note: candidates are: ll hash [10005]
 ll hash[10005];
    ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/stdexcept:39,
                 from /usr/include/c++/7/array:39,
                 from /usr/include/c++/7/tuple:39,
                 from /usr/include/c++/7/bits/stl_map.h:63,
                 from /usr/include/c++/7/map:61,
                 from palindrome.cpp:2:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:53:3: error: reference to 'hash' is ambiguous
   hash[i] = (hash[i-1]+cur*(str[i]-'a')%mod)%mod;
   ^~~~
palindrome.cpp:10:4: note: candidates are: ll hash [10005]
 ll hash[10005];
    ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/stdexcept:39,
                 from /usr/include/c++/7/array:39,
                 from /usr/include/c++/7/tuple:39,
                 from /usr/include/c++/7/bits/stl_map.h:63,
                 from /usr/include/c++/7/map:61,
                 from palindrome.cpp:2:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp:53:14: error: reference to 'hash' is ambiguous
   hash[i] = (hash[i-1]+cur*(str[i]-'a')%mod)%mod;
              ^~~~
palindrome.cpp:10:4: note: candidates are: ll hash [10005]
 ll hash[10005];
    ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/stdexcept:39,
                 from /usr/include/c++/7/array:39,
                 from /usr/include/c++/7/tuple:39,
                 from /usr/include/c++/7/bits/stl_map.h:63,
                 from /usr/include/c++/7/map:61,
                 from palindrome.cpp:2:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",str);
  ~~~~~^~~~~~~~~~