oj.uz

Submission #716688

# Submission time Handle Problem Language Result Execution time Memory
716688 2023-03-30T19:33:25 Z thiago_bastos Palindromes (APIO14_palindrome) C++17
100 / 100
 847 ms 45532 KB 
#include "bits/stdc++.h"

using namespace std;
 
#define INF   1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second
 
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
using i128 = __int128;

struct Hash {
	static const i64 P;
	static i64 B;
	vector<i64> pw, h;

	i64 mul(i64 a, i64 b) {
		i128 c = (i128)a * b;
		c = (c & P) + (c >> 61);
		if(c >= P) c -= P;
		return c;
	}

	i64 sum(i64 a, i64 b) {
		a += b;
		if(a >= P) a -= P;
		return a;
	}

	Hash(string& s) {
		int n = s.size();
		pw.resize(n + 1);
		h.resize(n + 1);
		pw[0] = 1;
		h[0] = 0;
		for(int i = 1; i <= n; ++i) {
			pw[i] = mul(pw[i - 1], B);
			h[i] = sum(h[i - 1], mul(pw[i], s[i - 1]));
		}
	}

	i64 operator()(int l, int r) {
		int n = pw.size();
		return mul(pw[n-l-1], sum(h[r+1], P - h[l]));
	}
};

mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
 
i64 uniform(i64 l, i64 r) {
	uniform_int_distribution<i64> uid(l, r);
	return uid(rng);
}

const i64 Hash :: P = (1ll << 61) - 1;
i64 Hash :: B = uniform(256, (1ll << 61) - 2);

void manacher(string& s, vector<int>& d1, vector<int>& d2) {
	int l = 0, r = -1, len = 0, n = s.size();
	d1.assign(n, 1);
	d2.assign(n, 0);
	for(int i = 0; i < n; ++i) {
		if(i <= r) {
			d1[i] = min(d1[l + r - i], r - i + 1);
			d2[i] = min(d2[l + r - i + 1], r - i + 1);
		}
		while(i + d1[i] < n && i - d1[i] >= 0 && s[i - d1[i]] == s[i + d1[i]]) ++d1[i];
		while(i + d2[i] < n && i - d2[i] - 1 >= 0 && s[i - d2[i] - 1] == s[i + d2[i]]) ++d2[i];
		if(r < i + d2[i] - 1) l = i - d2[i], r = i + d2[i] - 1;
		if(r < i + d1[i] - 1) l = i - d1[i] + 1, r = i + d1[i] - 1;		
		if(r == n - 1) len = max(len, r - l + 1);
	}
}	

i64 f(string& s) {
	Hash hs(s);
	using T = pair<int, i64>;
	map<T, int, greater<T>> mp;
	map<i64, ii> interval;
	vector<int> d1, d2;
	int n = s.size();
	
	manacher(s, d1, d2);

	for(int i = 0; i < n; ++i) {
		i64 h = hs(i - d1[i] + 1, i + d1[i] - 1);
		++mp[{2 * d1[i] - 1, h}];
		interval[h] = {i - d1[i] + 1, i + d1[i] - 1};
		if(d2[i]) {
			h = hs(i - d2[i], i + d2[i] - 1);
			++mp[{2 * d2[i], h}];
			interval[h] = {i - d2[i], i + d2[i] - 1};
		}
	}

	i64 ans = 0;

	while(!mp.empty()) {
		auto [len, h] = mp.begin()->fi;
		int frq = mp.begin()->sc;
		ans = max(ans, (i64)len * frq);
		mp.erase(mp.begin());
		if(len <= 2) continue;
		auto [l, r] = interval[h];
		i64 nh = hs(l + 1, r - 1);
		mp[{len - 2, nh}] += frq;
		interval[nh] = {l + 1, r - 1};
	}

	return ans;
}

void solve() {
	string s;
	cin >> s;
	cout << f(s) << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
  	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 252 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 296 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1748 KB Output is correct
2 Correct 8 ms 1268 KB Output is correct
3 Correct 10 ms 1824 KB Output is correct
4 Correct 10 ms 1748 KB Output is correct
5 Correct 5 ms 1160 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 11 ms 1644 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 4 ms 980 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 15308 KB Output is correct
2 Correct 134 ms 12560 KB Output is correct
3 Correct 209 ms 15296 KB Output is correct
4 Correct 196 ms 15340 KB Output is correct
5 Correct 70 ms 8952 KB Output is correct
6 Correct 58 ms 7204 KB Output is correct
7 Correct 114 ms 10228 KB Output is correct
8 Correct 10 ms 2908 KB Output is correct
9 Correct 33 ms 5616 KB Output is correct
10 Correct 53 ms 8000 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 26456 KB Output is correct
2 Correct 520 ms 29452 KB Output is correct
3 Correct 777 ms 45108 KB Output is correct
4 Correct 847 ms 45532 KB Output is correct
5 Correct 252 ms 26660 KB Output is correct
6 Correct 480 ms 31748 KB Output is correct
7 Correct 501 ms 29864 KB Output is correct
8 Correct 31 ms 8028 KB Output is correct
9 Correct 30 ms 8028 KB Output is correct
10 Correct 209 ms 23312 KB Output is correct
11 Correct 368 ms 26668 KB Output is correct
12 Correct 63 ms 11460 KB Output is correct