Submission #535139

#	Time	Username	Problem	Language	Result	Execution time	Memory
535139		getac	Palindromes (APIO14_palindrome)	C++17	73 / 100	1092 ms	38740 KiB

palindrome

//InTheNameOfGOD
//PRS;)
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i < r; ++i)
#define per(i, l, r) for(int i = r - 1; i >= l; --i)
#define Fast cin.tie(0) -> sync_with_stdio(0);
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
#define X first
#define Y second
typedef long long ll;
using namespace std;
typedef pair<int, pair<int, int>> pi;
constexpr ll mod = 2e9 + 11;
constexpr int xn = 3e5 + 1;
int b[xn << 1][20], a[xn], t[xn];
pi c[xn];
ll h1[xn], h2[xn], p[xn];
char s[xn];
inline int lcp(int x, int y)
{
	int mn = min(t[x], t[y]), ret = 0;
	per(i, 0, 19) if(ret + (1 << i) <= mn && b[x + ret][i] == b[y + ret][i]) ret += (1 << i);
	return ret;
}
inline bool cmp(int x, int y)
{
	int z = lcp(x, y);
	if(t[y] <= z) return 0;
	if(t[x] <= z) return 1;
	return s[x + z] < s[y + z];
}
inline ll mk(ll x, ll y, int z)
{
	y = (y * p[z]) % mod, x -= y;
	return x < 0 ? x + mod : x;
}
int main()
{
	Fast
	scanf("%s", &s);
	int n = strlen(s);
	rep(i, 0, n) b[i][0] = s[i] - 'a' + 1;
	rep(j, 1, 20)
	{
		int j1 = j - 1;
		rep(i, 0, n) c[i] = {b[i][j1], {b[i + (1 << j1)][j1], i}};
		sort(c, c + n);
		b[c[0].Y.Y][j] = 1;
		rep(i, 1, n)
		{
			b[c[i].Y.Y][j] = b[c[i - 1].Y.Y][j];
			if(c[i - 1].X < c[i].X || c[i - 1].Y.X < c[i].Y.X) b[c[i].Y.Y][j]++;
		}
	}
	h1[0] = h2[n] = 0, p[0] = 1;
	rep(i, 0, n) h1[i + 1] = (h1[i] * 27 + s[i] - 'a' + 1) % mod;
	per(i, 0, n) h2[i] = (h2[i + 1] * 27 + s[i] - 'a' + 1) % mod;
	rep(i, 1, n + 1) p[i] = (p[i - 1] * 27) % mod;
	ll ans = 1;
	rep(i, 0, n)
	{
		int l = 2, r = min(n - i, i + 1) + 1;
		while(l < r)
		{
			int md = l + r >> 1;
			mk(h1[i + md], h1[i], md) == mk(h2[i - md + 1], h2[i + 1], md) ? l = md + 1 : r = md;
		}
		t[i] = l - 1;
		ans = max(ans, (t[i] << 1) - 1);
	}
	rep(i, 0, n) a[i] = i;
	sort(a, a + n, cmp);
	vector<pi> v;
	rep(i, 1, n)
	{
		int e = lcp(a[i - 1], a[i]), prs = 0;
		while(!v.empty() && v.back().X >= e)
		{
			pi j = v.back();
			v.pop_back();
			if(j.X > e) ans = max(ans, 1ll * ((j.X << 1) - 1) * (i - j.Y.X));
		}
		if(!v.empty()) prs = v.back().Y.Y;
		v.push_back({e, {prs, i}});
	}
	rep(i, 0, n)
	{
		int l = 1, r = min(n - i, i) + 1;
		while(l < r)
		{
			int md = l + r >> 1;
			mk(h1[i + md], h1[i], md) == mk(h2[i - md], h2[i], md) ? l = md + 1 : r = md;
		}
		t[i] = l - 1;
		ans = max(ans, t[i] << 1);
	}
	sort(a, a + n, cmp);
	for(pi i : v) ans = max(ans, 1ll * ((i.X << 1) - 1) * (n - i.Y.X));
	v.clear();
	rep(i, 1, n)
	{
		int e = lcp(a[i - 1], a[i]), prs = 0;
		while(!v.empty() && v.back().X >= e)
		{
			pi j = v.back();
			v.pop_back();
			if(j.X > e) ans = max(ans, 1ll * (j.X << 1) * (i - j.Y.X));
		}
		if(!v.empty()) prs = v.back().Y.Y;
		v.push_back({e, {prs, i}});
	}
	for(pi i : v) ans = max(ans, 1ll * (i.X << 1) * (n - i.Y.X));
	printf("%lld\n", ans);
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:43:10: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300001]' [-Wformat=]
   43 |  scanf("%s", &s);
      |         ~^   ~~
      |          |   |
      |          |   char (*)[300001]
      |          char*
palindrome.cpp:68:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |    int md = l + r >> 1;
      |             ~~^~~
palindrome.cpp:94:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |    int md = l + r >> 1;
      |             ~~^~~
palindrome.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%s", &s);
      |  ~~~~~^~~~~~~~~~

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