oj.uz

Submission #535676

# Submission time Handle Problem Language Result Execution time Memory
535676 2022-03-10T22:23:01 Z pooyashams Palindromes (APIO14_palindrome) C++17
73 / 100
 1000 ms 47208 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 1 ms 724 KB Output is correct
22 Correct 1 ms 724 KB Output is correct
23 Correct 1 ms 724 KB Output is correct
24 Correct 1 ms 724 KB Output is correct
25 Correct 1 ms 724 KB Output is correct
26 Correct 1 ms 724 KB Output is correct
27 Correct 1 ms 724 KB Output is correct
28 Correct 1 ms 724 KB Output is correct
29 Correct 1 ms 724 KB Output is correct
30 Correct 1 ms 724 KB Output is correct
31 Correct 1 ms 724 KB Output is correct
32 Correct 1 ms 724 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 980 KB Output is correct
2 Correct 5 ms 980 KB Output is correct
3 Correct 4 ms 980 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 5 ms 984 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 5 ms 980 KB Output is correct
8 Correct 4 ms 984 KB Output is correct
9 Correct 5 ms 972 KB Output is correct
10 Correct 4 ms 980 KB Output is correct
11 Correct 5 ms 980 KB Output is correct
12 Correct 5 ms 980 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3660 KB Output is correct
2 Correct 47 ms 3716 KB Output is correct
3 Correct 54 ms 3632 KB Output is correct
4 Correct 62 ms 3608 KB Output is correct
5 Correct 56 ms 3664 KB Output is correct
6 Correct 51 ms 3608 KB Output is correct
7 Correct 43 ms 3676 KB Output is correct
8 Correct 46 ms 3720 KB Output is correct
9 Correct 63 ms 3668 KB Output is correct
10 Correct 56 ms 3684 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 31104 KB Output is correct
2 Correct 577 ms 31088 KB Output is correct
3 Correct 634 ms 31040 KB Output is correct
4 Correct 605 ms 31176 KB Output is correct
5 Correct 709 ms 31108 KB Output is correct
6 Correct 660 ms 31248 KB Output is correct
7 Correct 629 ms 31128 KB Output is correct
8 Correct 665 ms 31052 KB Output is correct
9 Correct 661 ms 31208 KB Output is correct
10 Correct 748 ms 31072 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 47208 KB Time limit exceeded
2 Halted 0 ms 0 KB -