Submission #1137966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137966		Math4Life2020	Palindromes (APIO14_palindrome)	C++20	47 / 100	590 ms	174796 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll a = 1234567; const ll p = 1e9+7; //hash values 
ll ans = 0;

const ll Nm = 6e5+5; ll N;
ll aexp[Nm+1];

ll phsh[Nm+1];
ll pihsh[Nm+1];
ll tval[Nm];
ll prad[Nm]; //permutation radius

ll ghsh(ll l, ll r) { //[l,r]
	ll v = phsh[r+1]-aexp[r+1-l]*phsh[l];
	v = (v+p*(-v/p+2))%p;
	return v;
}

ll gihsh(ll l0, ll r0) { //[l,r]
	ll l = Nm-1-r0; ll r = Nm-1-l0;
	ll v = pihsh[r+1]-aexp[r+1-l]*pihsh[l];
	v = (v+p*(-v/p+2))%p;
	return v;
}

unordered_map<ll,ll> fdeg; //forward degree (hash -> children)
unordered_map<ll,ll> radj; //reverse adjacency (parent -> this)
unordered_map<ll,ll> hrad; //radius of hash
unordered_map<ll,ll> ival; //intrinsic value

inline void aug(unordered_map<ll,ll>& m0, ll v, ll del=1) {
	if (m0.find(v)!=m0.end()) {
		m0[v]+=del;
	} else {
		m0[v]=del;
	}
}

//ll CLOCK = 0;

void process(vector<ll> velem, ll l, ll r) {
	// cout << "process: l,r="<<l<<","<<r<<"\nvelem:\n";
	// for (ll x: velem) {
	// 	cout << x << " ";
	// }
	// cout << "\n";
	// if (CLOCK++>=4) {
	// 	exit(0);
	// }
	if (velem.size()==0) {
		return;
	}
	ll M = velem.size();
	vector<ll> v0,v1;
	for (ll i=0;i<M;i++) {
		ll x = velem[i];
		if (prad[x]>=l) {
			v0.push_back(ghsh(x,x+l));
			hrad[v0[i]]=l;
			aug(ival,v0[i],0);
			aug(fdeg,v0[i],0);
		} else {
			assert(1==2);
			v0.push_back(-1);
		}
	}
	for (ll i=0;i<M;i++) {
		ll x = velem[i];
		if (prad[x]>=r) {
			v1.push_back(ghsh(x,x+r));
			hrad[v1[i]]=r;
			aug(ival,v1[i],0);
			aug(fdeg,v1[i],0);
		} else {
			v1.push_back(-1);
		}
	}
	//v1 shouldn't have repeats other than -1s
	//repeats possibly present in v0? also no -1s
	if ((r-1)==l) { //process
		for (ll i=0;i<M;i++) {
			if (v1[i]==-1) {
				aug(ival,v0[i]);
				// cout << "aug ival for x,rad="<<velem[i]<<","<<l<<"\n";
				radj[v0[i]]=-1;
			} else {
				radj[v1[i]]=v0[i];
				aug(fdeg,v0[i]);
			}
		}
		return;
	} 
	if (M==1) {
		if (v1[0]!=-1) {
			radj[v1[0]]=v0[0];
			aug(fdeg,v0[0]);
		} else {
			ll shsh = ghsh(velem[0],velem[0]+prad[velem[0]]);
			if (shsh==v0[0]) {
				aug(ival,v0[0]);
				radj[v0[0]]=-1;
			} else {
				aug(ival,shsh);
				radj[shsh]=v0[0];
				aug(fdeg,v0[0]);
				aug(fdeg,shsh,0);
				hrad[shsh]=prad[velem[0]];
			}
		}
		return;
	}
	ll xn = (l+r)/2;
	vector<ll> v2;
	for (ll i=0;i<M;i++) {
		ll x = velem[i];
		if (prad[x]>=xn) {
			v2.push_back(ghsh(x,x+xn));
			hrad[v2[i]]=xn;
			aug(ival,v2[i],0);
			aug(fdeg,v2[i],0);
		} else {
			v2.push_back(-1);
		}
	}
	// unordered_map<ll,vector<ll>> vhsh;
	// for (ll i=0;i<M;i++) {
	// 	vhsh[v2[i]].push_back(velem[i]);
	// }
	// vector<ll> pr1;
	// for (auto A0: vhsh) {
	// 	if (A0.first!=-1) {
	// 		process(A0.second,xn,r);
	// 		pr1.push_back((A0.second)[0]);
	// 	} else {
	// 		for (ll x: A0.second) {
	// 			pr1.push_back(x);
	// 		}
	// 	}
	// }
	// process(pr1,l,xn);
	unordered_map<ll,vector<ll>> vhsh;
	for (ll i=0;i<M;i++) {
		vhsh[v2[i]].push_back(i);
	}
	vector<ll> pr1;
	for (auto A0: vhsh) {
		if (A0.first!=-1) {
			vector<ll> vpr;
			for (ll x: A0.second) {
				vpr.push_back(velem[x]);
			}
			process(vpr,xn,r);
			pr1.push_back((A0.second)[0]);
		} else {
			for (ll x: A0.second) {
				pr1.push_back(x);
			}
		}
	}
	// cout << "processing back: l,r="<<l<<","<<r<<"\n";
	// cout << "pr1 size="<<pr1.size()<<"\n";
	unordered_map<ll,vector<ll>> vhsh1;
	for (ll x: pr1) {
		vhsh1[v0[x]].push_back(velem[x]);
	}
	for (auto A0: vhsh1) {
		process(A0.second,l,xn);
	}
}

queue<ll> q0;

int main() {
	mt19937 gen((long long) new char);
	aexp[0]=1;
	for (ll i=0;i<Nm;i++) {
		aexp[i+1]=(a*aexp[i])%p;
	}
	ios_base::sync_with_stdio(false); cin.tie(0);
	string s; cin >> s;
	string t="|";
	N = s.length();
	for (ll i=0;i<N;i++) {
		t += s.substr(i,1);
		t+="|";
	}
	N=t.length(); 
	//cout << "N="<<N<<"\n";
	for (ll i=0;i<N;i++) {
		tval[i]=t[i];
	}
	// for (ll i=N;i<Nm;i++) {
	// 	tval[i]=gen();
	// }
	phsh[0]=0;
	for (ll i=0;i<Nm;i++) {
		phsh[i+1]=(tval[i]+a*phsh[i])%p;
	}
	pihsh[0]=0;
	for (ll i=0;i<Nm;i++) {
		pihsh[i+1]=(tval[Nm-1-i]+a*pihsh[i])%p;
	}
	vector<ll> vall;
	for (ll i=0;i<N;i++) { //get radii
		vall.push_back(i);
		ll rmin = 0;
		ll rmax = min(i,N-1-i);
		while (rmin<rmax) {
			ll rt = (rmin+rmax+1)/2;
			if (ghsh(i,i+rt)==gihsh(i-rt,i)) {
				rmin = rt;
			} else {
				rmax = rt-1;
			}
		}
		prad[i]=rmin;
		//cout << "prad[i="<<i<<"]="<<prad[i]<<"\n";
	}
	process(vall,0,N+5);
	//cout << "ghsh: "<<ghsh(1,2)<<"\n";
	for (pii p0: fdeg) {
		if (p0.second==0) {
			q0.push(p0.first);
		}
	}
	while (!q0.empty()) {
		ll hv = q0.front(); q0.pop();
		//cout << "process hv = "<<hv<<"\n";
		ll rhv = hrad[hv];
		ll ncnt = ival[hv];
		//cout << "rhv,ncnt="<<rhv<<","<<ncnt<<"\n";
		ans = max(ans,rhv*ncnt);
		ll rad = radj[hv];
		if (rad != -1) {
			fdeg[rad]--;
			if (fdeg[rad]==0) {
				q0.push(rad);
			}
			aug(ival,rad,ival[hv]);
		}
	}
	if (ghsh(0,N-1)==gihsh(0,N-1)) {
		ans = max(ans,(N-1)/2);
	}
	cout << ans << "\n";
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27