Submission #1116355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116355		raczek	Palindromes (APIO14_palindrome)	C++17	65 / 100	1060 ms	96636 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG 
auto& operator <<(auto& o, __int128_t x) {return o<<(long long)x;}
auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cerr<<"["#X"]: "<<X<<endl;
#else
#define debug(X) {}
#endif
#pragma GCC optimize "unroll-loops"
#pragma GCC optimize "fast-math"
#pragma GCC optimize "Ofast"
#define __int128_t long long
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
struct hashTab
{
	const __int128_t MOD = 1e9+7;
	const __int128_t R = 195250661;
	const __int128_t X = 379;
	vector<__int128_t> rev;
	vector<__int128_t> pot;
	vector<__int128_t> hs;
	vector<__int128_t> rhs;
	int n;
	__int128_t mulp(__int128_t a, __int128_t b)
	{
		return (a * b)%MOD;
	}
	__int128_t add(__int128_t a, __int128_t b)
	{
		__int128_t c = a+b;
		if(c < 0) c += MOD;
		if(c >= MOD) return c - MOD;
		return c;
	}
	hashTab(string s)
	{
//		debug(MOD);
		n = s.size();
		rev.resize(n);
		rev[0] = R;
		pot.resize(n);
		pot[0] = X;
		hs.resize(n);
		rhs.resize(n);
		for(int i=1;i<n;i++)
			pot[i] = mulp(pot[i-1], X), rev[i] = mulp(rev[i-1], R);
		for(int i=0;i<n;i++)
			hs[i] = add(mulp((s[i]), pot[i]), (i > 0 ? hs[i-1] : 0)),
				rhs[i] = add(mulp((s[i]), pot[n-i-1]), (i > 0 ? rhs[i-1] : 0));
//		debug(hs);
//		debug(rhs);
	}
	__int128_t get(int x, int y, bool f)
	{
		assert(x >= 0 && y < hs.size() && x <= y);
		if(!f)
			return mulp(add(hs[y], -(x > 0 ? hs[x-1] : 0)), (x > 0 ? rev[x-1] : 1));
		return mulp(add(rhs[y], -(x > 0 ? rhs[x-1] : 0)), (y < n-1 ? rev[n - (y+1) - 1] : 1));
	}
};
vector<pair<int, int> > getIdx(string s)
{
	string t;
	for(auto v : s)
		t += string("#") + v;
	s = t+"#";
//	debug(s);
	hashTab A(s);
	unordered_map<__int128_t, pair<int, int> > idx;
	auto check = [&](int x, int r)
	{
		if(x - r < 0) return false;
		if(x + r >= s.size()) return false;
//		debug(x-r);
//		debug(x+r);
//		debug(A.get(x-r, x, 0));
//		debug(A.get(x, x+r, 1));
		if(A.get(x-r, x, 0) == A.get(x, x+r, 1))
			if(idx.find(A.get(x-r, x+r, 0)) == idx.end())
				return true;
		return false;
	};
	for(int i=s.size()-1;i>=0;i--)
	{
//		debug(i);
		int p = -1, q = s.size();
		while(p != q-1)
		{
			int pol = (p+q) >> 1;
			if(check(i, pol))
				p = pol;
			else
				q = pol;
		}
//		debug(q);
		for(int j=0;j<q;j++)
			idx[A.get(i - j, i + j, 0)] = make_pair(i - j, j*2+1);
	}
	vector<pair<int, int> > res;
	for(auto v : idx)
		if(v.second.first%2 == 1)
		{
			if(s[v.second.first + v.second.second] == '#')
				res.push_back({v.second.first/2, (v.second.second+1)/2});
			else
				res.push_back({v.second.first/2, v.second.second/2});
		}
	return res;
}
struct SuffixArray {
	vector<int> sa, lcp, rank;
	SuffixArray(string& s, int lim=256) {
		int n = sz(s) + 1, k = 0, a, b;
		vector<int> x(all(s)), y(n), ws(max(n, lim));
		x.push_back(0), sa = lcp = y, iota(all(sa), 0);
		for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
			p = j, iota(all(y), n - j);
			rep(i,0,n) if (sa[i] >= j) y[p++] = sa[i] - j;
			fill(all(ws), 0);
			rep(i,0,n) ws[x[i]]++;
			rep(i,1,lim) ws[i] += ws[i - 1];
			for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
			swap(x, y), p = 1, x[sa[0]] = 0;
			rep(i,1,n) a = sa[i - 1], b = sa[i], x[b] =
				(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
		}
		for (int i = 0, j; i < n - 1; lcp[x[i++]] = k)
			for (k && k--, j = sa[x[i] - 1];
					s[i + k] == s[j + k]; k++);
		rank = x;
	}
};
const int K = 19;
const int base = 1<<K;
struct rmq
{
	int st[K+1][base];
	int lg[base+1];
	int bnd;
	rmq(vector<int> array)
	{
		bnd = array.size();
		lg[1] = 0;
		for (int i = 2; i <= base; i++)
			lg[i] = lg[i/2] + 1;
		std::copy(array.begin(), array.end(), st[0]);
		for (int i = 1; i <= K; i++)
		    for (int j = 0; j + (1 << i) <= base; j++)
		        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
	}
	int query(int L, int R)
	{
	//	assert(L <= R);
		if(R >= bnd) return -1e9;
		int i = lg[R - L + 1];
		return min(st[i][L], st[i][R - (1 << i) + 1]);
	}
};
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin>>s;
	vector<pair<int, int> > pals = getIdx(s);
	debug(pals);
	SuffixArray A(s);
	long long res = 0;
	vector<int> LCP;
	for(int i=2;i<A.lcp.size();i++)
		LCP.push_back(A.lcp[i]);
	debug(LCP);
	rmq B(LCP);
	auto bs = [&](int r, int val, int sgn)
	{
		int p = -1, q = s.size()+2, pol;
		while(p != q-1)
		{
			pol = (p+q) >> 1;
			if(r + sgn*pol >= 0 && B.query(min(r + sgn*pol, r), max(r + sgn*pol, r)) >= val)
				p = pol;
			else
				q = pol;
		}
		if(p == -1) return p;
		return r + p*sgn;
	};
	for(auto v : pals)
	{
		if(res > (long long)v.second * (long long)(s.size() - v.second + 1)) continue;
		debug(v);
		int ans = 1;
		int r = A.rank[v.first];
		debug(r);
		pair<int, int> p;
		p.first = bs(r, v.second, -1);
		p.second = bs(r, v.second, 1);
		debug(p);
		if(p.first != -1 && p.second != -1)
			ans = p.second - p.first + 2;
		else
			ans = 1;
		if(r > 0)
		{
			pair<int, int> d;
			d.first = bs(r-1, v.second, -1);
			d.second = bs(r-1, v.second, 1);
			if(d.first != -1 && d.second != -1)
				ans = max(ans, d.second - d.first + 2);
		}
		res = max(res, (long long)ans*(long long)v.second);
	}
	cout<<res;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from palindrome.cpp:1:
palindrome.cpp: In member function 'long long int hashTab::get(int, int, bool)':
palindrome.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   assert(x >= 0 && y < hs.size() && x <= y);
      |                    ~~^~~~~~~~~~~
palindrome.cpp: In lambda function:
palindrome.cpp:77:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   if(x + r >= s.size()) return false;
      |      ~~~~~~^~~~~~~~~~~
palindrome.cpp: In function 'int32_t main()':
palindrome.cpp:175:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |  for(int i=2;i<A.lcp.size();i++)
      |              ~^~~~~~~~~~~~~

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