제출 #42019

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42019		Aidyn_A	회문 (APIO14_palindrome)	C++14	23 / 100	1068 ms	14968 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)1e6 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;
const int P = 31;

void megaRandom() {
	unsigned int FOR;
 	asm("rdtsc" : "=A"(FOR));
  srand(FOR);
}                                               

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;
unordered_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);
	megaRandom();
	cnt.reserve(1000000);
	cin >> s;
	h[0] = s[0];
	for(int i = 1; i < sz(s); i ++)
		h[i] = add(mult(h[i - 1], P), s[i]);	
	for(int i = 0; i < sz(s); i ++) {
		int len = 1;
		cnt[get_hash(i, i)] ++;
		while(i - len >= 0 && i + len < sz(s) && s[i - len] == s[i + len]) {
			cnt[get_hash(i - len, i + len)] ++;
			len ++;
		}
	}
	ll res = 0;
	for(int i = 0; i < sz(s); i ++) {
		int len = 1;
		res = max(res, 1ll * cnt[get_hash(i, i)]);
		while(i - len >= 0 && i + len < sz(s) && s[i - len] == s[i + len]) {
			res = max(res, 1ll * (len * 2 + 1) * cnt[get_hash(i - len, i + len)]);
			//cout << "l, r: " << i - len << ' ' << i + len << " len: " << len << " cnt: " << cnt[get_hash(i - len, i + len)] << "\n";
			len ++;
		}
	}
	//_____________________________________________
	cnt.clear();
	cnt.reserve(1000000);
	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]) {
			//cout << "l, r: " << i - len - 1 << ' ' << i + len << " len: " << len << " cnt: " << cnt[get_hash(i - len - 1, i + len)] << "\n";
			res = max(res, 1ll * (len + 1) * 2 * cnt[get_hash(i - len - 1, i + len)]);
			len ++;
		}
	}
	cout << res;
	return 0;  
}

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