Submission #537104

#	Time	Username	Problem	Language	Result	Execution time	Memory
537104		pooyashams	Palindromes (APIO14_palindrome)	C++14	73 / 100	1006 ms	99916 KiB

palindrome

#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#pragma GCC optimize("Ofast")
#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;
typedef vector<int> vi;
 
const int maxn = 3e5+10;
const int lgmx = 20;

#define rep(i,l,r) for (int i = l; i < r; i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define getat(a,x,y) a[((x)*lgmx)+(y)]

struct RMQ
{
	vi vals;
	int n;
	RMQ(){}
	RMQ(vi arr)
	{
		n = arr.size();
		vals = vi(lgmx*n, 0);
		for(int i = 0; i < n; i++)
			getat(vals, i, 0) = arr[i];
		for(int k = 1; k < lgmx; k++)
		{
			int x = (1<<(k-1));
			for(int i = 0; i < n; i++)
			{
				if(i+x < n)
					getat(vals, i, k) = min(getat(vals, i, k-1), getat(vals, i+x, k-1));
				else
					getat(vals, i, k) = getat(vals, i, k-1);
			}
		}
	}
	int get(int i, int j)
	{
		if(i == j)
			return vals[i*lgmx+0];
		int k = __lg(j-i);
		return min( getat(vals, i, k), getat(vals, j-(1<<k), k) );
	}
};

struct SuffixArray {
	int n;
	vi sa;
	vi lcp;
	vi rev;
	RMQ rlcp;
	SuffixArray(){};
	SuffixArray(string& s, int lim=256) {
		n = sz(s) + 1;
		int k = 0, a, b;
		vi x(all(s)+1), y(n), ws(max(n, lim)), rank(n);
		rev = vi(n);
		sa = lcp = y, iota(all(sa), 0);
		for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
			p = j, iota(all(y), n - j);
			rep(i,0,n) if (sa[i] >= j) y[p++] = sa[i] - j;
			fill(all(ws), 0);
			rep(i,0,n) ws[x[i]]++;
			rep(i,1,lim) ws[i] += ws[i - 1];
			for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
			swap(x, y), p = 1, x[sa[0]] = 0;
			rep(i,1,n) a = sa[i - 1], b = sa[i], x[b] =
				(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
		}
		rep(i,1,n) rank[sa[i]] = i;
		rep(i,0,n) rev[sa[i]] = i;
		for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
			for (k && k--, j = sa[rank[i] - 1];
					s[i + k] == s[j + k]; k++);
		rlcp = RMQ(lcp);
	}
	inline int getlcp(int i, int j)
	{
		if(i == j) return n-1-i;
		//if(i == 59) cerr << i << " " << j << endl;
		i = rev[i];
		j = rev[j];
		if(i > j) swap(i, j);
		return rlcp.get(i+1, j+1);
	}
} sfx;

int L[maxn];
int R[maxn];
 
int mr[maxn]; // practically lcp(sfxa[rev[i]], sfxa[rev[i]-1]) + i
int mc[maxn]; // 
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)
{
	mjm[0][0] = 0;
	for(int i = 1; i < n; i++)
	{
		//cerr << "alive " << i << endl;
		mjm[0][i] = i-sfx.getlcp(i, n+n+1-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)
{
	mjm[0][0] = 0;
	mjm[0][n-1] = n-1;
	for(int i = 1; i < n-1; i++)
	{
		mjm[0][i] = i-sfx.getlcp(i+1, n+n+1-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;
	}
	sfx = SuffixArray(s);
	L[1] = 0;
	R[n] = n+1;
	for(int i = 2; i <= n; i++) for(L[i] = i-1; L[i] > 0 and sfx.lcp[L[i]] >= sfx.lcp[i]; L[i] = L[L[i]]);
	for(int i = n-1; i >= 1; i--) for(R[i] = i+1; R[i] <= n and sfx.lcp[R[i]] >= sfx.lcp[i]; R[i] = R[R[i]]);
	//for(int i = 0; i < ss; i++) cerr << sfxa[i] << " "; cerr << endl;
	//for(int i = 0; i <= n; i++) cerr << sfx.lcp[i] << " "; cerr << endl;
	//for(int i = 0; i <= n; i++) cerr << L[i] << " "; cerr << endl;
	//for(int i = 0; i <= n; i++) cerr << R[i] << " "; cerr << endl;
	mr[sfx.sa[0]] = -1;
	mc[sfx.sa[0]] = -1;
	for(int i = 1; i <= n; i++)
	{
		int l = sfx.sa[i];
		mr[l] = l+sfx.lcp[i];
		mc[l] = R[i]-L[i];
		//cerr << l << ": " << mc[l] << " " << mr[l] << endl;
	}
	//
	string t = s;
	reverse(t.begin(), t.end());
	t = s+"#"+t;
	sfx = SuffixArray(t);
	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