Submission #1172829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172829		nuutsnoynton	Savez (COCI15_savez)	C++20	120 / 120	201 ms	708 KiB

savez

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 2e6 + 2;
const ll M = 43;
const ll mod = 1e9 + 9;
ll inv, pre_hash[N];
map < ll, ll > D;

ll Pow(ll a, ll b) {
	if ( b == 0) return 1;
	if ( b == 1) return a % mod;
	ll r = Pow(a, b/2);
	r = r * r % mod;
	if ( b % 2 == 1) r = r * a % mod;
	return r;
}

ll Find_pre(ll lo , ll hi) {
	ll r= pre_hash[hi];
	if ( lo > 0) r = r - pre_hash[lo - 1];
	r = (r % mod + mod) % mod;
	r = r * Pow(inv, lo) % mod;
	return r;
}

ll ans = 0;
void Go() {
	ll s, i, p, r;
	string str;
	
	cin >> str;

	s = 0;
	for (i = 0; i < str.size(); i ++) {
		s = s + (Pow(M, i) * (str[i] - 'A' + 2));
		pre_hash[i] = s;
	}
	p = Find_pre(0, str.size() - 1);
	D[p] ++;
	for (i = 1; i < str.size(); i ++) {
		s =  Find_pre(0, i - 1);
		r = Find_pre(str.size() - i, str.size() - 1);
		if (r == s) {
			D[p] = max(D[p], D[r] + 1);
		}
	}
	ans = max(ans, D[p]);
}

int main() {
	ll n, i;
	inv = Pow(M, mod - 2);
	cin >> n;
	
	for (i = 1; i <= n; i ++) {
		Go();
	}
	cout << ans << endl;
}

• 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