oj.uz

Submission #392638

# Submission time Handle Problem Language Result Execution time Memory
392638 2021-04-21T11:55:48 Z Berted Palindromes (APIO14_palindrome) C++17
100 / 100
 913 ms 61196 KB 
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define ll long long
using namespace std;

const int SZ = 2;
const ll MD[2] = {1000000007, 420691273};
const ll P[2] = {41, 31};

int N;
ll inv[SZ][300001];

inline ll exp(ll b, ll e, const ll& m)
{
	ll ret = 1;
	while (e)
	{
		if (e & 1) ret = ret * b % m;
		b = b * b % m; e >>= 1;
	}
	return ret;
}

inline void compInverse()
{
	for (int i = 0; i < SZ; i++) {inv[i][0] = 1; inv[i][1] = exp(P[i], MD[i] - 2, MD[i]); }

	for (int i = 2; i <= N; i++)
		for (int j = 0; j < SZ; j++) inv[j][i] = inv[j][i - 1] * inv[j][1] % MD[j];
}

struct RHash
{
	vector<ll> pref[SZ];
	ll K[SZ];
	
	void build(const string &s)
	{
		for (int j = 0; j < SZ; j++) 
		{
			pref[j].assign(s.size() + 1, 0);
			K[j] = 1;
		}
		
		for (int i = 1; i <= s.size(); i++)
		{
			for (int j = 0; j < SZ; j++)
			{
				pref[j][i] = (pref[j][i - 1] + K[j] * (s[i - 1] - 'a' + 1) % MD[j]) % MD[j];
				K[j] = K[j] * P[j] % MD[j];
			}
		}
	}

	inline array<ll, SZ> getHash(int L, int R)
	{
		array<ll, SZ> ret;
		for (int i = 0; i < SZ; i++)
		{
			ret[i] = pref[i][R] - pref[i][L - 1];
			if (ret[i] < 0) ret[i] += MD[i];
			ret[i] = (ret[i] * inv[i][L - 1]) % MD[i];
		}
		return ret;
	}
};

string S, T;
RHash A, B;

ll res = 0;
int ptr = 1, cnt[350001], sz[350001];
map<array<ll, SZ>, int> mp;
vector<int> adj[350001]; 

void DFS(int u)
{
	for (const auto &v : adj[u])
	{
		DFS(v); cnt[u] += cnt[v];
	}
	//cerr << "DFS:" << u << " " << sz[u] << " " << cnt[u] << "\n";
	res = max(res, (ll)cnt[u] * sz[u]);
}

int main()
{
	//freopen("A.in", "r", stdin);
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> S; N = S.size();

	compInverse();
	T = S; reverse(T.begin(), T.end());

	A.build(S); B.build(T);
	for (int i = 0; i < N; i++)
	{
		int L = 1, R = min(i, N - 1 - i) + 1;
		while (L < R)
		{
			int M = L + R >> 1;
			if (A.getHash(i + 1, i + M + 1) == B.getHash(N - i, N - i + M)) {L = M + 1;}
			else {R = M;}
		}
		//cerr << "Solving palindrome: " << i - L + 1 << " " << i << " " << i + L - 1 << "\n";
		array<ll, SZ> cur; int pv = -1;
		for (int j = i + L; j > i; j--)
		{
			cur = A.getHash(i + 1, j);
			if (mp.count(cur))
			{
				if (pv == -1) cnt[mp[cur]]++;
				else adj[mp[cur]].push_back(pv);
				pv = -1; break;	
			}
			else
			{
				//cerr << ptr << " represents " << i << " " << j - 1 << "\n";
				//cerr << cur[0] << " " << cur[1] << "\n";
				sz[ptr] = 2 * (j - i) - 1; mp[cur] = ptr++;
				if (pv == -1) cnt[mp[cur]]++;
				else adj[mp[cur]].push_back(pv);
				pv = mp[cur];
			}
		}
		if (pv != -1) adj[0].push_back(pv);
	}

	DFS(0);
	
	for (int i = 0; i < ptr; i++) {adj[i].clear(); cnt[i] = 0; sz[i] = 0;}
	mp.clear(); ptr = 1;

	for (int i = 1; i < N; i++)
	{
		int L = 1, R = min(i, N - i) + 1;
		while (L < R)
		{
			int M = L + R >> 1;
			if (A.getHash(i + 1, i + M) == B.getHash(N - i + 1, N - i + M)) {L = M + 1;}
			else {R = M;}
		}
		L--;
		//cerr << "Solving palindrome2: " << i - L << " " << i - 1 << " " << i << " " << i + L - 1 << "\n";
		if (L)
		{
			array<ll, SZ> cur; int pv = -1;
			for (int j = i + L; j > i; j--)
			{
				cur = A.getHash(i + 1, j);
				if (mp.count(cur))
				{
					if (pv == -1) cnt[mp[cur]]++;
					else adj[mp[cur]].push_back(pv);
					pv = -1; break;	
				}
				else
				{
					sz[ptr] = 2 * (j - i); mp[cur] = ptr++;
					if (pv == -1) cnt[mp[cur]]++;
					else adj[mp[cur]].push_back(pv);
					pv = mp[cur];
				}
			}
			if (pv != -1) adj[0].push_back(pv);
		}
	}

	DFS(0);

	cout << res << "\n";
	return 0;
}

Compilation message

palindrome.cpp: In member function 'void RHash::build(const string&)':
palindrome.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int i = 1; i <= s.size(); i++)
      |                   ~~^~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:103:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |    int M = L + R >> 1;
      |            ~~^~~
palindrome.cpp:141:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  141 |    int M = L + R >> 1;
      |            ~~^~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8680 KB Output is correct
2 Correct 6 ms 8688 KB Output is correct
3 Correct 7 ms 8652 KB Output is correct
4 Correct 6 ms 8680 KB Output is correct
5 Correct 6 ms 8652 KB Output is correct
6 Correct 6 ms 8652 KB Output is correct
7 Correct 6 ms 8664 KB Output is correct
8 Correct 6 ms 8652 KB Output is correct
9 Correct 6 ms 8652 KB Output is correct
10 Correct 6 ms 8524 KB Output is correct
11 Correct 6 ms 8524 KB Output is correct
12 Correct 6 ms 8652 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10320 KB Output is correct
2 Correct 19 ms 10204 KB Output is correct
3 Correct 19 ms 9816 KB Output is correct
4 Correct 20 ms 9716 KB Output is correct
5 Correct 16 ms 10192 KB Output is correct
6 Correct 17 ms 10100 KB Output is correct
7 Correct 19 ms 10120 KB Output is correct
8 Correct 10 ms 9040 KB Output is correct
9 Correct 9 ms 9036 KB Output is correct
10 Correct 17 ms 9856 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 25960 KB Output is correct
2 Correct 206 ms 25008 KB Output is correct
3 Correct 215 ms 20976 KB Output is correct
4 Correct 209 ms 20052 KB Output is correct
5 Correct 181 ms 25276 KB Output is correct
6 Correct 139 ms 21700 KB Output is correct
7 Correct 172 ms 20328 KB Output is correct
8 Correct 60 ms 13632 KB Output is correct
9 Correct 84 ms 15244 KB Output is correct
10 Correct 160 ms 23664 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 791 ms 61016 KB Output is correct
2 Correct 787 ms 55928 KB Output is correct
3 Correct 913 ms 45828 KB Output is correct
4 Correct 875 ms 41328 KB Output is correct
5 Correct 597 ms 60240 KB Output is correct
6 Correct 669 ms 48124 KB Output is correct
7 Correct 651 ms 44120 KB Output is correct
8 Correct 182 ms 23680 KB Output is correct
9 Correct 224 ms 23648 KB Output is correct
10 Correct 504 ms 54604 KB Output is correct
11 Correct 717 ms 61196 KB Output is correct
12 Correct 237 ms 25712 KB Output is correct