Submission #617275

#	Time	Username	Problem	Language	Result	Execution time	Memory
617275		HappyPacMan	Palinilap (COI16_palinilap)	C++14	0 / 100	44 ms	29944 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 3;
const int mod[] = {928193747,999281939};
int pow26[2][maxn],hprefix[2][18][maxn],hsuffix[2][18][maxn];
ll addi[26][maxn],odd[maxn],even[maxn],prefix[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	string s;
	cin >> s;
	int n = s.size();

	// Precompute 26^k
	pow26[0][0] = pow26[1][0] = 1;
	for(int i=0;i<n;i++){
		pow26[0][i+1] = (26ll*pow26[0][i])%mod[0];
		pow26[1][i+1] = (26ll*pow26[1][i])%mod[1];
	}

	// Precompute Hashing and Sparse Table
	for(int i=0;i<n;i++){
		hprefix[0][0][i] = hprefix[1][0][i] = hsuffix[0][0][i] = hsuffix[1][0][i] = s[i]-'a';
	}
	for(int i=1;i<18;i++){
		for(int j=0;j+(1<<i)<=n;j++){
			hprefix[0][i][j] = (hprefix[0][i-1][j]+1ll*pow26[0][1<<(i-1)]*hprefix[0][i-1][j+(1<<(i-1))])%mod[0];
			hprefix[1][i][j] = (hprefix[1][i-1][j]+1ll*pow26[1][1<<(i-1)]*hprefix[1][i-1][j+(1<<(i-1))])%mod[1];
		}
		for(int j=n-1;j-(1<<i)>=-1;j--){
			hsuffix[0][i][j] = (hsuffix[0][i-1][j]+1ll*pow26[0][1<<(i-1)]*hsuffix[0][i-1][j-(1<<(i-1))])%mod[0];
			hsuffix[1][i][j] = (hsuffix[1][i-1][j]+1ll*pow26[1][1<<(i-1)]*hsuffix[1][i-1][j-(1<<(i-1))])%mod[1];
		}
	}
	for(int i=0;i<n-1;i++){
		if(i > 0){
			int z = 0;
			for(int j=17;j>=0;j--){
				if(i-1-z-(1<<j) >= -1 && i+1+z+(1<<j) <= n && hsuffix[0][j][i-1-z] == hprefix[0][j][i+1+z] && hsuffix[1][j][i-1-z] == hprefix[1][j][i+1+z]){
					odd[i] += (1<<j);
					z += (1<<j);
				}
			}
			prefix[i-z+1]--;
			prefix[i+1]++;
			prefix[i+1]++;
			prefix[i+z+1]--;
			// cout << i-z+1 << ' ' << i+1 << ' ' << i+z+1 << '\n';
			z++;
			if(i-1-z >= -1 && i+1+z <= n){
				addi[s[i+z]-'a'][i-z]++;
				addi[s[i-z]-'a'][i+z]++;
				int l = i-1-z, r = i+1+z, v = 0;
				for(int j=17;j>=0;j--){
					if(l-v-(1<<j) >= -1 && r+v+(1<<j) <= n && hsuffix[0][j][l-v] == hprefix[0][j][r+v] && hsuffix[1][j][l-v] == hprefix[1][j][r+v]){
						addi[s[i+z]-'a'][i-z] += (1<<j);
						addi[s[i-z]-'a'][i+z] += (1<<j);
						v += (1<<j);
					}
				}
			}
		}
		int z = 0;
		for(int j=17;j>=0;j--){
			if(i-z-(1<<j) >= -1 && i+1+z+(1<<j) <= n && hsuffix[0][j][i-z] == hprefix[0][j][i+1+z] && hsuffix[1][j][i-z] == hprefix[1][j][i+1+z]){
				even[i] += (1<<j);
				z += (1<<j);
			}
		}
		prefix[i-z+1]--;
		prefix[i+1]++;
		prefix[i+2]++;
		prefix[i+z+2]--;	
		// cout << i << ' ' << z << " -> " << i-z+1 << ' ' << i+1 << ' ' << i+2 << ' ' << i+z+2 << '\n';
		z++;
		if(i-z >= -1 && i+1+z <= n){
			addi[s[i+z]-'a'][i-z+1]++;
			addi[s[i-z+1]-'a'][i+z]++;
			int l = i-z, r = i+1+z, v = 0;
			for(int j=17;j>=0;j--){
				if(l-v-(1<<j) >= -1 && r+v+(1<<j) <= n && hsuffix[0][j][l-v] == hprefix[0][j][r+v] && hsuffix[1][j][l-v] == hprefix[1][j][r+v]){
					addi[s[i+z]-'a'][i-z+1] += (1<<j);
					addi[s[i-z+1]-'a'][i+z] += (1<<j);
					v += (1<<j);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		prefix[i] += prefix[i-1];
	}
	for(int i=1;i<=n;i++){
		prefix[i] += prefix[i-1];
	}
	ll tot = 0;
	for(int i=0;i<=n;i++){
		tot += odd[i]+even[i];
	}
	for(int i=0;i<=n;i++){
		prefix[i] += tot;
	}
	ll res = 0;
	for(int i=0;i<n;i++){
		res += odd[i] + even[i];
	}
	for(int i=0;i<n;i++){
		ll mx = 0;
		for(int j=0;j<26;j++){
			// cout << addi[j][i] << " ";
			mx = max(mx,addi[j][i]);
		}
		// cout << "\n";
		res = max(res,mx+prefix[i]+odd[i]);
	}
	cout << res + n << '\n';
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46