Submission #42030

#	Time	Username	Problem	Language	Result	Execution time	Memory
42030		Aidyn_A	Palindromes (APIO14_palindrome)	C++14	8 / 100	1072 ms	40200 KiB

palindrome

#include <stdio.h>
#include <bits/stdc++.h>			

#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()
#define what_is(x) #x << " is " << (x)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = (int)1e4 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e7 + 7;
const int P = 31;

int mult(int a, int b) {
	return 1ll * a * b % MOD;
}

int add(int a, int b) {
	a += b;
	if(a >= MOD) a -= MOD;
	return a;
}

int subs(int a, int b) {
	a -= b;
	if(a < 0) a += MOD;
	return a;
}

string s;
int cnt[(int)1e7 + 10];
//map<int, int> cnt;
int pw[N];
int h[N];


int get_hash(int l, int r) {
	return subs(h[r], mult(h[l - 1], pw[r - l + 1]));
}

int main() {
	pw[0] = 1;
	for(int i = 1; i <= N - 123; i ++)
		pw[i] = mult(pw[i - 1], P);
	cin >> s;
	//cnt.reserve(500000);
	h[0] = s[0];
	for(int i = 1; i < sz(s); i ++)
		h[i] = add(mult(h[i - 1], P), s[i]);	
	int res = 0;
	for(int i = 0; i < sz(s); i ++) {
		int len = 1;
		cnt[s[i]] ++;
		while(i - len >= 0 && i + len < sz(s) && s[i - len] == s[i + len]) {
			cnt[get_hash(i - len, i + len)] ++;
			len ++;
		}
	}
	for(int i = 0; i < sz(s); i ++) {
		int len = 1;
		res = max(res, cnt[s[i]]);
		while(i - len >= 0 && i + len < sz(s) && s[i - len] == s[i + len]) {
			res = max(res, (len * 2 + 1) * cnt[get_hash(i - len, i + len)]);
			len ++;
		}
	}
	//_____________________________________________
	for(int i = 0; i < sz(s); i ++) {
		int len = 0;
		while(i - len - 1 >= 0 && i + len < sz(s) && s[i - len - 1] == s[i + len]) {
			cnt[get_hash(i - len - 1, i + len)] ++;
			len ++;
		}
	}
	for(int i = 0; i < sz(s); i ++) {
		int len = 0;
		while(i - len - 1 >= 0 && i + len < sz(s) && s[i - len - 1] == s[i + len]) {
			res = max(res, (len + 1) * 2 * cnt[get_hash(i - len - 1, i + len)]);
			len ++;
		}
	}
	cout << res;
	return 0;  
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:72:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   cnt[s[i]] ++;
           ^
palindrome.cpp:80:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   res = max(res, cnt[s[i]]);
                          ^

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