Submission #368006

#	Time	Username	Problem	Language	Result	Execution time	Memory
368006		AriaH	Palindromes (APIO14_palindrome)	C++11	73 / 100	1008 ms	36040 KiB

palindrome

/** Im the best because i work as hard as i possibly can **/

#pragma GCC optimize("Ofast, unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 3e5 + 10;
const ll mod = 884577481;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 19;
const ll base = 609859;

string s;

char C[N];

int n, T, P[N], rnk[LOG][N], seg[N << 2];

ll pw[N], hshL[N], hshR[N];

bool cmp(int i, int j)
{
	int t = T - 1;
	if(rnk[t][i] == rnk[t][j])
	{
		if(max(i, j) + (1 << t) > n) return i > j;
		return rnk[t][i + (1 << t)] < rnk[t][j + (1 << t)];
	}
	return rnk[t][i] < rnk[t][j];
}

inline ll baze(int l, int r)
{
	return (hshL[r] - (hshL[l - 1] * pw[r - l + 1] % mod) + mod) % mod;
}

inline ll baze2(int l, int r)
{
	return (hshR[l] - (hshR[r + 1] * pw[r - l + 1] % mod) + mod) % mod;
}

inline void SA()
{
	pw[0] = 1;
	for(int i = 1; i < N; i ++) pw[i] = pw[i - 1] * base % mod;
	for(int i = 1; i <= n; i ++)
	{
		hshL[i] = (hshL[i - 1] * base + s[i] - 'a' + 1) % mod;
		P[i] = i;
		rnk[0][i] = s[i] - 'a' + 1;
	}
	for(int i = n; i >= 1; i --)
	{
		hshR[i] = (hshR[i + 1] * base + s[i] - 'a' + 1) % mod;
	}
	for(T = 1; T < LOG; T ++)
	{
		sort(P + 1, P + n + 1, cmp);
		rnk[T][P[1]] = 1;
		for(int i = 2; i <= n ;i ++)
		{
			rnk[T][P[i]] = rnk[T][P[i - 1]] + cmp(P[i - 1], P[i]);
		}
	}
}

int lcp(int i, int j)
{
	int ret = 0;
	for(T = LOG - 1; ~T; T --)
	{
		if(max(i, j) + (1 << T) - 1 > n || rnk[T][i] != rnk[T][j]) continue;
		ret ^= 1 << T;
		i += 1 << T;
		j += 1 << T;
	}
	return ret;
}

void build(int v = 1, int tl = 1, int tr = n)
{
	if(tl == tr)
	{
		seg[v] = lcp(P[tl - 1], P[tl]);
		return;
	}
	int mid = (tl + tr) >> 1;
	build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
	seg[v] = min(seg[v << 1], seg[v << 1 | 1]);
}

int find_nxt(int p, int x, int v = 1, int tl = 1, int tr = n)
{
	if(p > n) return n + 1;
	if(tr < p) return -1;
	if(seg[v] >= x)
	{
		if(tr == n) return n + 1;
		return -1;
	}
	if(tl == tr) return tl;
	int mid = (tl + tr) >> 1;
	int cu = find_nxt(p, x, v << 1, tl, mid);
	if(cu == -1) cu = find_nxt(p, x, v << 1 | 1, mid + 1, tr);
	return cu;
}

int find_prv(int p, int x, int v = 1, int tl = 1, int tr = n)
{
	if(tl > p) return -1;
	if(seg[v] >= x)
	{
		if(tl == 1) return 0;
		return -1;
	}
	if(tl == tr) return tl;
	int mid = (tl + tr) >> 1;
	int cu = find_prv(p, x, v << 1 | 1, mid + 1, tr);
	if(cu == -1) cu = find_prv(p, x, v << 1, tl, mid);
	return cu;
}

ll calc(int l, int r)
{
	int sz = r - l + 1, id = rnk[LOG - 1][l];
	int L = find_prv(id, sz);
	int R = find_nxt(id + 1, sz);
	return R - L;
}

int main()
{
    scanf("%s", C);
	n = strlen(C);
	s = C;
	s = "#" + s;
	SA();
	build();
	ll tot = 0;
	for(int i = 1; i <= n; i ++)
	{
		int d = 0, up = min(i - 1, n - i) + 1;
		while(up - d > 1)
		{
			int mid = (up + d) >> 1;
			if(baze(i, i + mid) == baze2(i - mid, i)) d = mid;
			else up = mid;
		}
		tot = max(tot, calc(i - d, i + d) * (2 * d + 1));
	}
	for(int i = 1; i < n; i ++)
	{
		if(s[i] != s[i + 1]) continue;
		int d = 0, up = min(i - 1, n - i - 1) + 1;
		while(up - d > 1)
		{
			int mid = (up + d) >> 1;
			if(baze(i + 1, i + 1 + mid) == baze2(i - mid, i)) d = mid;
			else up = mid;
		}
		tot = max(tot, calc(i - d, i + d + 1) * (2 *  d + 2));
	}
	printf("%lld", tot);
	return 0;
}

Compilation message (stderr)

palindrome.cpp:3:43: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("Ofast, unroll-loops")
      |                                           ^
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
    4 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
      |                                                                 ^
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.cpp:4:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
palindrome.c

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