제출 #535676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535676		pooyashams	회문 (APIO14_palindrome)	C++17	73 / 100	1090 ms	47208 KiB

palindrome

#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 3e5+10;
const int lgmx = 20;

int rnk[lgmx][maxn*2];
int P[maxn*2];
int on[maxn*2];
int st[2];
int sz[2];
char S[maxn*2];
int ss = 0;
int f, pw;

int sfxa[maxn*2];
int lcpa[maxn*2];
int rev[maxn*2];

int L[maxn*2];
int R[maxn*2];

inline bool cmp(int i, int j)
{
	if(rnk[f-1][i] < rnk[f-1][j]) return true;
	if(rnk[f-1][i] > rnk[f-1][j]) return false;
	int a = -1;
	int b = -1;
	if( i+pw < st[on[i]]+sz[on[i]] ) a = rnk[f-1][i+pw];
	if( j+pw < st[on[j]]+sz[on[j]] ) b = rnk[f-1][j+pw];
	return a < b;
}

inline int lcp(int i, int j)
{
	if(i == j) return st[on[i]]+sz[on[i]]-i;
	int m = 0;
	for(int k = lgmx-1; k >= 0; k--)
	{
		int x = (1<<k);
		if(i+m+x <= st[on[i]]+sz[on[i]] and j+m+x <= st[on[j]]+sz[on[j]])
			if(rnk[k][i+m] == rnk[k][j+m])
				m += x;
	}
	return m;
}

inline void bsfxa()
{
	iota(P, P+ss, 0);
	sort(P, P+ss, [&](int i, int j){return S[i] < S[j];});
	rnk[0][P[0]] = 0;
	for(int i = 1; i < ss; i++)
		rnk[0][P[i]] = rnk[0][P[i-1]] + (S[P[i]] != S[P[i-1]]);
	for(f = 1, pw = 1; f < lgmx; f++, pw*=2)
	{
		sort(P, P+ss, cmp);
		rnk[f][P[0]] = 0;
		for(int i = 1; i < ss; i++)
			rnk[f][P[i]] = rnk[f][P[i-1]] + cmp(P[i-1], P[i]);
	}
	iota(sfxa, sfxa+ss, 0);
	sort(sfxa, sfxa+ss, [&](int i, int j){return rnk[lgmx-1][i] < rnk[lgmx-1][j];});
	for(int i = 1; i < ss; i++)
		lcpa[i] = lcp(sfxa[i], sfxa[i-1]);
	for(int i = 0; i < ss; i++)
		rev[sfxa[i]] = i;
	lcpa[0] = -1;
	lcpa[ss] = -1;
	L[0] = L[ss] = 0;
	R[0] = R[ss] = ss;
	for(int i = 1; i < ss; i++) for(L[i] = i-1; lcpa[L[i]] >= lcpa[i]; L[i] = L[L[i]]);
	for(int i = ss-1; i > 0; i--) for(R[i] = i+1; lcpa[R[i]] >= lcpa[i]; R[i] = R[R[i]]);
	//
}

int mr[maxn]; // practically lcp(sfxa[rev[i]], sfxa[rev[i]-1]) + i
int mc[maxn]; // 
int mpl[maxn]; // max palindrome (even/odd)
int mjm[lgmx][maxn]; // j-mpl[j] (min)

ll ans = 0;

inline int getmn(int l, int r) // [l, r)
{
	int k = __lg(r-l);
	return min(mjm[k][l], mjm[k][r-(1<<k)]);
}

inline int mxpl(int l, int r) // [l, r)
{
	if(r == l) return 0;
	if(r-l == 1) return 0; // even
	int i = l;
	while(r-l > 1)
	{
		int k = __lg(r-l-1);
		int m = r - (1<<k);
		if(mjm[k][m] > i)
			r = m;
		else
			l = m;
	}
	return l-i;
}

inline void pmjm(int n)
{
	for(int k = 1; k < lgmx; k++)
	{
		int x = (1 << (k-1));
		for(int i = 0; i < n; i++)
		{
			if(i+x < n)
				mjm[k][i] = min(mjm[k-1][i], mjm[k-1][i+x]);
			else
				mjm[k][i] = mjm[k-1][i];
		}
	}
}

inline void calce(int n)
{
	mpl[0] = 0;
	mjm[0][0] = 0;
	for(int i = 1; i < n; i++)
	{
		mpl[i] = lcp(i, ss-i);
		mjm[0][i] = i-mpl[i];
	}
	pmjm(n);
	for(int i = 0; i < n-1; i++)
		ans = max(ans, 2ll*mxpl(i, (i+n)/2+1));
	for(int i = 0; i < n; i++)
	{
		if(mr[i] == -1 or mr[i] == i or mr[i] == i+1) continue;
		int x = mxpl(i, (i+mr[i])/2+1);
		ans = max(ans, 2ll*mc[i]*x);
	}
}

inline void calco(int n)
{
	mpl[0] = 0;
	mjm[0][0] = 0;
	mpl[n-1] = 0;
	mjm[0][n-1] = n-1;
	for(int i = 1; i < n-1; i++)
	{
		mpl[i] = lcp(i+1, ss-i);
		mjm[0][i] = i-mpl[i];
	}
	pmjm(n);
	for(int i = 0; i < n-1; i++)
		ans = max(ans, 2ll*mxpl(i, (i+n+1)/2)+1 );
	for(int i = 0; i < n; i++)
	{
		if(mr[i] == -1 or mr[i] == i) continue;
		int x = mxpl(i, (i+mr[i]+1)/2);
		ans = max(ans, 2ll*mc[i]*x+mc[i]);
	}
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin >> s;
	const int n = s.size();
	if(n == 1)
	{
		cout << 1 << endl;
		return 0;
	}
	fill(on, on+n, 0);
	fill(on+n, on+n+n, 1);
	st[0] = 0;
	st[1] = n;
	sz[0] = sz[1] = n;
	ss = n;
	for(int i = 0; i < n; i++)
		S[i] = S[n+n-1-i] = s[i];
	bsfxa();
	//for(int i = 0; i < ss; i++) cerr << sfxa[i] << " "; cerr << endl;
	//for(int i = 0; i < ss; i++) cerr << lcpa[i] << " "; cerr << endl;
	//for(int i = 0; i < ss; i++) cerr << L[i] << " "; cerr << endl;
	//for(int i = 0; i < ss; i++) cerr << R[i] << " "; cerr << endl;
	mr[sfxa[0]] = -1;
	mc[sfxa[0]] = -1;
	for(int i = 1; i < n; i++)
	{
		int l = sfxa[i];
		mr[l] = l+lcpa[i];
		mc[l] = R[i]-L[i];
		//cerr << l << ": " << mc[l] << " " << mr[l] << endl;
	}
	//
	ss = n+n;
	bsfxa();
	calce(n);
	calco(n);
	cout << ans << endl;
	return 0;
}

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