Submission #104297

#	Time	Username	Problem	Language	Result	Execution time	Memory
104297		dupreez	Palindromes (APIO14_palindrome)	C++14	23 / 100	284 ms	21924 KiB

palindrome

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <vector>
#include <stack>
#include <unordered_map>
#define mk make_pair
#define pb push_back
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll, ll> pos;
const ll MOD = 1000000007,N=1010;
const ull b = MOD;
string s,s2;
unsigned long long int hs[N],bs[N];
ll ans = 0;
unordered_map<ull, int> mp[N];

ull hsh(int i1, int i2) {
	ull v1 = hs[i1] - hs[i2 + 1];
	v1 *= bs[i1];
	return v1;
}

int main() {
	cin >> s;
	bs[0] = 1;
	for (int i = 1; i < N; i++)bs[i] = bs[i - 1] * b;
	for (int i = s.size() - 1; i >= 0; i--) {
		hs[i] = hs[i + 1] +((ull)s[i] - 'a') * bs[s.size() - 1 - i];
	}
	for (int i1 = 0; i1 < s.size(); i1++) {
		for (int i2 = i1; i2 < s.size(); i2++) {
			mp[i2 - i1 + 1][hsh(i1,i2)]++;
		}
	}

	for (int i1 = 0; i1 < s.size(); i1++) {
		for (int i2 = 0; i1 + i2 < s.size() && i1 - i2 >= 0; i2++) {
			if (s[i1 + i2] != s[i1 - i2])break;
			ll v1 = i2 * 2 + 1, v2 = mp[v1][hsh(i1 - i2, i1 + i2)];
			ans = max(ans, v1 * v2);
		}
		for (int i2 = 0; i1 +1+i2 < s.size() && i1 - i2 >= 0; i2++) {
			if (s[i1 + i2 + 1] != s[i1 - i2])break;
			ll v1 = i2 * 2 + 2, v2 = mp[v1][hsh(i1 - i2, i1 + i2 + 1)];
			ans = max(ans, v1 * v2);
		}
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:36:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i1 = 0; i1 < s.size(); i1++) {
                   ~~~^~~~~~~~~~
palindrome.cpp:37:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i2 = i1; i2 < s.size(); i2++) {
                     ~~~^~~~~~~~~~
palindrome.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i1 = 0; i1 < s.size(); i1++) {
                   ~~~^~~~~~~~~~
palindrome.cpp:43:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i2 = 0; i1 + i2 < s.size() && i1 - i2 >= 0; i2++) {
                    ~~~~~~~~^~~~~~~~~~
palindrome.cpp:48:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i2 = 0; i1 +1+i2 < s.size() && i1 - i2 >= 0; i2++) {
                    ~~~~~~~~~^~~~~~~~~~

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