Submission #1138145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138145		Math4Life2020	Palindromes (APIO14_palindrome)	C++20	47 / 100	240 ms	171000 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;
}

struct Node {
	int fdeg = 0;
	int ival = 0;
	int xp; //x position
	int hrad;
	ll radj=-1;
	ll hashv;
	Node(ll x0, ll rad0) {
		xp = x0; hrad = rad0;
		if (hrad<=prad[x0]) {
			hashv = ghsh(x0,x0+hrad);
		} else {
			hashv = -1;
		}
	}
};

vector<Node> MEM;

ll process(vector<ll> velem, vector<ll> memf, ll l, ll r) { //return location of root
	//vector of coordinates, vector of (at v1), left, right
	// cout << "process: l,r="<<l<<","<<r<<"\nvelem:\n";
	// for (ll x: velem) {
	// 	cout << x << " ";
	// }
	// cout << "\n";
	if (velem.size()==0) {
		assert(1==2);
		return -1;
	}
	ll M = velem.size();
	//memf stores v1
	if ((r-1)==l) { //process
		ll mem0 = MEM.size();
		MEM.push_back(Node(velem[0],l));
		for (ll i=0;i<M;i++) {
			if (memf[i]==-1) {
				MEM[mem0].ival++;
				//cout << "add source at x0,l="<<velem[0]<<","<<l<<"\n";
			} else {
				MEM[memf[i]].radj=mem0;
				MEM[mem0].fdeg++;
			}
		}
		return mem0;
	} 
	if (M==1) {
		ll mem0 = MEM.size();
		MEM.push_back(Node(velem[0],l));
		if (memf[0]!=-1) {
			MEM[memf[0]].radj=mem0;
			MEM[mem0].fdeg++;
		} else {
			ll x0 = velem[0]; ll rad0 = prad[velem[0]];
			if (l==rad0) {
				MEM[mem0].ival++;
				//cout << "add source at x0,l="<<x0<<","<<l<<"\n";
			} else {
				MEM.push_back(Node(x0,rad0));
				//cout << "create source node: x0,rad0="<<x0<<","<<rad0<<"\n";
				MEM[MEM.size()-1].ival++;
				MEM[MEM.size()-1].radj=mem0;
				MEM[mem0].fdeg++;
			}
		}
		return mem0;
	}
	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));
		} else {
			v2.push_back(-1);
		}
	}
	unordered_map<ll,vector<int>> vhsh;
	for (ll i=0;i<M;i++) {
		vhsh[v2[i]].push_back(i);
	}
	vector<pair<ll,vector<int>>> vhshN;
	for (auto A0: vhsh) {
		vhshN.push_back(A0);
	}
	vhsh.clear();
	vector<ll> xloc,mloc;
	for (auto A0: vhshN) {
		if (A0.first==-1) {
			for (ll x: A0.second) {
				xloc.push_back(velem[x]);
				mloc.push_back(-1);
			}
		} else {
			xloc.push_back(velem[(A0.second)[0]]);
			vector<ll> xloc2,mloc2;
			for (ll x: A0.second) {
				xloc2.push_back(velem[x]);
				mloc2.push_back(memf[x]);
			}
			mloc.push_back(process(xloc2,mloc2,xn,r));
		}
	}
	return process(xloc,mloc,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;
	vector<ll> vm1(N,-1);
	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,vm1,-1,N+5);
	//cout << "ghsh: "<<ghsh(1,2)<<"\n";
	for (ll POS=0;POS<MEM.size();POS++) {
		if (MEM[POS].fdeg==0) {
			q0.push(POS);
		}
	}
	while (!q0.empty()) {
		ll madd = q0.front(); q0.pop();
		ans = max((ll)ans,(ll)MEM[madd].ival*MEM[madd].hrad);
		//cout << "ival,hrad="<<MEM[madd].ival<<","<<MEM[madd].hrad<<"\n";
		ll rad = MEM[madd].radj;
		if (rad != -1) {
			//fdeg[rad]--;
			MEM[rad].fdeg--;
			if (MEM[rad].fdeg==0) {
				q0.push(rad);
			}
			assert(MEM[rad].fdeg>=0);
			//aug(ival,rad,ival[hv]);
			MEM[rad].ival+=MEM[madd].ival;
		}
	}
	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