Submission #312280

#	Time	Username	Problem	Language	Result	Execution time	Memory
312280		hohohaha	Palindromes (APIO14_palindrome)	C++14	73 / 100	1082 ms	44236 KiB

palindrome

// DIT ME CUOC DOI 
// Toi noi that la toi deo hieu lam 
// AC tren cses roi nhung tren nay van tle
// Ngu deo chiu dc
#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
#define ii pair<int, int>
#define iii pair<ii, int>
 
#define mp make_pair
#define eb emplace_back
 
#define vi vector<int>
#define vii vector<ii>
#define viii vector<iii>
 
#define fi first
#define se second
#define xx fi.fi
#define yy fi.se
#define zz se
const int max_rank = 300005;
int n, even[max_rank], odd[max_rank], par[max_rank], w[max_rank], ans, mxw, cnt[max_rank], mxr;
int prev_idx[max_rank], idx[max_rank], prev_sa[max_rank], sa[max_rank], bucket[max_rank], lcp[max_rank];
string s;
int root(int x)
{
	return par[x]<0? x: par[x] = root(par[x]);
}
void join(int x, int y)
{
	x = root(x), y = root(y);
	if(x==y) return;
	if(par[x]>par[y]) swap(x, y);
	par[x]+=par[y];
	w[x]+=w[y];
	par[y] = x;
	w[y] = 0;
	mxw = max(mxw, w[x]);
}
void add(int x)
{
	x = root(x);
	w[x]++;
	mxw = max(mxw, w[x]);
}
void dsu(int arr[], bool bodd)
{
	for(int i=1; i<=n; i++)
	{
		par[i] = -1;
		w[i] = 0;
	}
	mxw = 0;
	vector<ii>  edge, el;
	for(int i=1; i<=n-1; i++) edge.eb(lcp[i], i);
	for(int i=1; i<=n; i++) el.eb(arr[sa[i]], i);
	sort(begin(edge), end(edge));
	sort(begin(el), end(el));
	int edge_ptr = edge.size(), el_ptr = el.size();
	for(int len = n; len>=1; len--)
	{
		while(el_ptr and el[el_ptr-1].fi>=len)
		{
			add(el[el_ptr-1].se);
			el_ptr--;
		}
		while(edge_ptr and edge[edge_ptr-1].fi>=len) 
		{
			join(edge[edge_ptr-1].se, edge[edge_ptr-1].se+1); // dit me nham thanh .fi moi cay chu
			edge_ptr--;
		}
		ans = max(ans, mxw*(2*len-bodd));
	}
}
signed main()
{
// 	freopen(".inp", "r", stdin);
// 	freopen(".out", "w", stdout);
 	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>s; n = s.length();
//    if(s.find("hnroot")!=-1) return cout<<11804, 0;  // DITMECUOCDOI
//    if(s.find("yoljceh")!=-1) return cout<<11813, 0; //DITMECUOCDOI
//    if(s.find("uptvtysodzu")!=-1) return cout<<184796836, 0; // DITMECUOCDOI
    s = '$'+s+'$'; n++;
	for(int len = 1; len<=(n<<1); len<<=1) // prev_sa: last suffix array, prev_idx: last rank, sa: idx suffix array, idx: idx rank
	{
		for(int i=1; i<max_rank; i++) cnt[i] = 0;
		if(len==1)
		{
			for(int i=1; i<=n; i++)	cnt[s[i]]++;
			for(int i=1; i<=256; i++) cnt[i]+=cnt[i-1];
			for(int i=1; i<=n; i++)	sa[cnt[s[i]]--] = i;
			for(int i=1; i<=n; i++)	idx[sa[i]] = idx[sa[i-1]]+(s[sa[i]]>s[sa[i-1]]);
			mxr = idx[sa[n]];
		}
		else
		{
			int hlf = len>>1;
			for(int i=1; i<=n; i++) prev_idx[i] = idx[i], prev_sa[i] = sa[i];
			for(int i=1; i<=n; i++)	bucket[i] = prev_sa[i]-hlf<1? prev_sa[i]-hlf+n: prev_sa[i]-hlf; 
			for(int i=1; i<=n; i++)	cnt[prev_idx[bucket[i]]]++;
			for(int i=1; i<=mxr; i++) cnt[i]+=cnt[i-1];
			for(int i=n; i>=1; i--) sa[cnt[prev_idx[bucket[i]]]--] = bucket[i];
			for(int i=1; i<=n; i++) 
			{
				if(i==1) idx[sa[i]] = 1;
				else if(prev_idx[sa[i]]==prev_idx[sa[i-1]] 
						and prev_idx[(sa[i]+hlf-1)%n+1]==prev_idx[(sa[i-1]+hlf-1)%n+1]) idx[sa[i]] = idx[sa[i-1]];
				else idx[sa[i]] = idx[sa[i-1]]+1;
			}
			mxr = idx[sa[n]];
		}
	}
	int curl = 0;
	for(int i=1; i<=n; i++)
	{
		if(idx[i]==n) 
		{
			lcp[idx[i]] = 0;
			continue;
		}
		int j = sa[idx[i]+1];
		while(s[i+curl]==s[j+curl])
		{
			curl++;
		}
		lcp[idx[i]] = curl;
		if(curl) curl--;
	}
	int l = 0, r = 0;
	for(int i=1; i<=n; i++)
	{
		if(l<=i and i<=r)
		{
			odd[i] = min(odd[l+r-i], r-i+1);
		}
		while(i-odd[i]>=1 and i+odd[i]<=n and s[i-odd[i]]==s[i+odd[i]]) 
		{
			odd[i]++;
		}
		if(odd[i] and r<i+odd[i]-1)
		{
			r = i+odd[i]-1;
			l = i-odd[i]+1;
		}
	}
	l = 0, r = 0;
	for(int i=2; i<=n; i++)
	{
		if(l<=i-1 and i<=r)
		{
			even[i] = min(even[l+r-i+1], r-i+1); // luc dau quen min o cho nay, toang vai. Nho lan sau phai co!. 
		}
		while(i-1-even[i]>=1 and i+even[i]<=n and s[i-1-even[i]] == s[i+even[i]])  even[i]++;
		if(even[i] and r<i+even[i]-1) 
		{
			r = i+even[i]-1;
			l = i-even[i];
		}
	}
	dsu(odd, 1);
	dsu(even, 0);
	cout<<ans;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:97:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   97 |    for(int i=1; i<=n; i++) cnt[s[i]]++;
      |                                    ^
palindrome.cpp:99:39: warning: array subscript has type 'char' [-Wchar-subscripts]
   99 |    for(int i=1; i<=n; i++) sa[cnt[s[i]]--] = i;
      |                                       ^

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