Submission #1265925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265925		canhnam357	Savez (COCI15_savez)	C++20	120 / 120	59 ms	31816 KiB

savez

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
const int mod1 = 1035972859;
const int mod2 = 1704760909;
const int base = 256;
const int N = 2e6 + 5;
int inv1[N], inv2[N], h1[N], h2[N];
int power(int a, int b, int mod)
{
	int res = 1;
	while (b)
	{
		if (b & 1) (res *= a) %= mod;
		(a *= a) %= mod;
		b >>= 1;
	}
	return res;
}
string s;
void cal()
{
	h1[0] = h2[0] = s[0];
	int p1 = 1, p2 = 1;
	for (int i = 1; i < s.size(); i++)
	{
		(p1 *= base) %= mod1;
		(p2 *= base) %= mod2;
		h1[i] = (h1[i - 1] + s[i] * p1) % mod1;
		h2[i] = (h2[i - 1] + s[i] * p2) % mod2;
	}
}
int get(int l, int r)
{
	if (l == 0) return h1[r] * h2[r];
	int f = ((h1[r] - h1[l - 1] + mod1) * inv1[l]) % mod1;
	int z = ((h2[r] - h2[l - 1] + mod2) * inv2[l]) % mod2;
	return f * z; 
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	inv1[N - 1] = power(power(base, N - 1, mod1), mod1 - 2, mod1);
	inv2[N - 1] = power(power(base, N - 1, mod2), mod2 - 2, mod2);
	for (int i = N - 2; i >= 0; i--)
	{
		inv1[i] = (inv1[i + 1] * base) % mod1;
		inv2[i] = (inv2[i + 1] * base) % mod2;
	}
	map<int, int> mp;
	int n;
	cin >> n;	
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		cal();
		int m = s.size();
		int k = h1[s.size() - 1] * h2[s.size() - 1];
		int z = 1;
		for (int j = 0; j < m; j++)
		{
			if (get(0, j) == get(m - j - 1, m - 1))
			{
				if (mp.count(get(0, j)))
				{
					ckmax(z, mp[get(0, j)] + 1);
				}
			}
		}
		ckmax(mp[k], z);
	}
	int ans = 0;
	for (auto x : mp) ckmax(ans, x.second);
	cout << ans;
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12