Submission #42259

#	Time	Username	Problem	Language	Result	Execution time	Memory
42259		fest	Palindromes (APIO14_palindrome)	C++14	0 / 100	530 ms	50512 KiB

palindrome

// fest
#include <bits/stdc++.h>	

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;

void FREOPEN() {
	#ifdef COMP
		freopen(".in", "r", stdin);
		freopen("2.out", "w", stdout);
	#endif
}                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

const int N = 300500, M = 21, inf = 1e9 * 2, MOD = (int)1e9 + 7;

char CH[N];

const ll INF = 1e18;

const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};

int n;

int pos[N], suff[N], c[M][N], new_suff[N], lcp[N], ans[N], dp[N], rev[N];

vector<int> go[N];

int range(int x) {
	while (x >= n) x -= n;
	while (x < 0) x += n;
	return x;
}

int main() {
  
	FREOPEN();
	scanf("%s", CH);
	string s = CH;
	s += '#';   
	n = SZ(s);
	for (int i = 0; i < n; i++) {
		c[0][i] = (int)(s[i] - '#');
		pos[c[0][i] + 1]++;
	}
	for (int i = 0; i < N - 1; i++) pos[i + 1] += pos[i];
	for (int i = 0; i < n; i++) {
		suff[pos[c[0][i]]++] = i;
	}
	for (int len = 0; (1 << len) <= n; len++) {
		memset(pos, 0, sizeof(pos));
		for (int i = 0; i < n; i++) {
			int f = range(suff[i] - (1 << len));
			pos[c[len][f] + 1]++;
		}
		for (int i = 0; i < N - 1; i++) pos[i + 1] += pos[i];
		for (int i = 0; i < n; i++) {
			int f = range(suff[i] - (1 << len));
			new_suff[pos[c[len][f]]++] = f;		
		}
		memcpy(suff, new_suff, sizeof(new_suff));
		c[len + 1][suff[0]] = 0;
		int C = 0;
		for (int i = 1; i < n; i++) {
			int ff = range(suff[i - 1] + (1 << len)), ss = range(suff[i] + (1 << len));
			if (c[len][suff[i - 1]] < c[len][suff[i]] || c[len][ff] < c[len][ss]) C++;
			c[len + 1][suff[i]] = C;
		}
	}
	for (int i = 1; i < n - 1; i++) {
		int p1 = suff[i], p2 = suff[i + 1];
		for (int j = M - 1; j >= 0; j--) {
			if (max(p1, p2) + (1 << j) >= n) continue;
			if (c[j][p1] == c[j][p2]) {
				lcp[i] += (1 << j);	
				p1 += (1 << j);
				p2 += (1 << j);
      }
		}
	}
	vector<pair<int, int> > st;
	for (int i = 1; i < n - 1; i++) {
		while (!st.empty() && st.back().F >= lcp[i]) st.pop_back();
		if (!st.empty()) ans[suff[i]] -= st.back().S;
		st.pb({lcp[i], i});
	} 
	st.clear();
	for (int i = n - 2; i >= 1; i--) {
		while (!st.empty() && st.back().F >= lcp[i]) st.pop_back();
		if (!st.empty()) ans[suff[i]] += st.back().S - 1;
		else ans[suff[i]] += n - 2;
		st.pb({lcp[i], i});
	}
	for (int i = 1; i < n; i++) rev[suff[i]] = i;
	ll out = 0;
	for (int i = 0, l = 0, r = 0; i < n - 1; i++) {
		dp[i] = 1;
		if (i <= r) dp[i] = min(dp[l + (r - i)], r - i + 1);
		while (i - dp[i] >= 0 && i + dp[i] < n - 1 && s[i - dp[i]] == s[i + dp[i]]) dp[i]++;
		if (i + dp[i] - 1 > r) l = i - dp[i] + 1, r = i + dp[i] - 1;
		out = max(out, dp[i] * 2ll - 1); 
	}                         
	vector<int> st2;
	for (int l = 0; l < n - 1; l++) {
		int r = (l + l + lcp[rev[l]] - 1) / 2;
		while (!st2.empty() && st2.back() - dp[st2.back()] + 1 >= l - dp[l] + 1) st2.pop_back();
		st2.pb(l);
		go[r].pb(l);
		while (!go[l].empty()) {
			int now = go[l].back();
			go[l].pop_back();
			int lef = 0;
			int rig = SZ(st2) - 1;
			int pos = -1;
			while (lef <= rig) {
				int mid = (lef + rig) / 2;
				if (st2[mid] - dp[st2[mid]] + 1 <= now) pos = st2[mid], lef = mid + 1;
				else rig = mid - 1;
			}
			if (pos >= now) out = max(out, ((pos - now) * 2 + 1) * 1ll * (ans[now] + 1));
		}
	}
	st2.clear();
	memset(dp, 0, sizeof(dp));
	for (int i = 1, l = 0, r = 0; i < n - 1; i++) {
		if (s[i] != s[i - 1]) continue;
		dp[i] = 1;
		if (i <= r) dp[i] = min(dp[l + (r - i + 1)], r - i + 1);
		while (i - dp[i] - 1 >= 0 && i + dp[i] < n - 1 && s[i - dp[i] - 1] == s[i + dp[i]]) dp[i]++;
		if (i + dp[i] - 1 > r) l = i - dp[i], r = i + dp[i] - 1;
		out = max(out, dp[i] * 2ll); 
	}                         
	for (int l = 1; l < n - 1; l++) {
		int r = (l + l + lcp[rev[l]]) / 2;
		while (!st2.empty() && st2.back() - dp[st2.back()] >= l - dp[l]) st2.pop_back();
		st2.pb(l);
		go[r].pb(l);
		while (!go[l].empty()) {
			int now = go[l].back();
			go[l].pop_back();
			int lef = 0;
			int rig = SZ(st2) - 1;
			int pos = -1;
			while (lef <= rig) {
				int mid = (lef + rig) / 2;
				if (st2[mid] - dp[st2[mid]] <= now) pos = st2[mid], lef = mid + 1;
				else rig = mid - 1;
			}
			if (pos - 1 >= now) out = max(out, ((pos - now) * 2) * 1ll * (ans[now] + 1));
		}
	}
	cout << out;
	return 0;	
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:53:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", CH);
                 ^

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