Submission #1116262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116262		raczek	Palindromes (APIO14_palindrome)	C++17	0 / 100	1057 ms	109852 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
struct hashTab
{
	const __int128_t MOD = 1000000000000000009;
	const __int128_t R = 68601583113456465;
	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)
	{
		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);
	set<pair<__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.lower_bound(make_pair(A.get(x-r, x+r, 0), make_pair(-1, -1)))->first != A.get(x-r, x+r, 0))
			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.insert(make_pair(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 sufAr
{
	int n;
	vector<int> cntSort;//[n+1]
	vector<int> order;//[n]
	vector<int> rank;
	vector<int> cp;
	vector<int> pt;
	void layerCompute(int k)//rank: i -> (1..n)
	{
//		debug(order);
//		debug(rank);
		if((1<<(k-1)) > n) return;
		auto Fill = [&](vector<int>& O, bool f)
		{
			fill(pt.begin(), pt.end(), -1);
			int p = f ? (1<<(k-1)) : 0;
			for(auto i : O)
			{
				int x = 0;
				if(i + p < n) x = rank[i+p];
				pt[i] = cntSort[x];
				cntSort[x] = i;
			}
		};
		auto Sort = [&](vector<int>& O)
		{
			O.clear();
			vector<int> q;
			for(int i=0;i<=n;i++)
			{
				while(cntSort[i] != -1)
				{q.push_back(cntSort[i]); cntSort[i] = pt[cntSort[i]];}
				while(q.size())
					{O.push_back(q.back()); q.pop_back();}
			}
		};
		for(int i=0;i<n;i++) order[i] = i;
		Fill(order, 1);
		Sort(order);
		debug(order);
		Fill(order, 0);
		Sort(order);
		int cnt = 1;
		cp = rank;
		rank[order[0]] = cnt++;
		for(int i=1;i<n;i++)
		{
			if(cp[order[i]] == cp[order[i-1]])
			{
				int a = (order[i] + (1<<(k-1)) < n) ? cp[order[i] + (1<<(k-1))] : 0;
				int b = (order[i-1] + (1<<(k-1)) < n) ? cp[order[i-1] + (1<<(k-1))] : 0;
				if(a == b) {rank[order[i]] = rank[order[i-1]]; continue;}
			}
			rank[order[i]] = cnt++;
		}
		layerCompute(k+1);
	}
	vector<int> LCP;
	void lcpCnt(string s)
	{
		LCP.resize(n-1);
		int k = 0;
		for(auto& v : rank) --v;
		for(int i=0;i<n;i++)
		{
			if(rank[i] == n-1){k = 0; continue;}
			int j = order[rank[i] + 1];
			while(i + k < n && j + k  < n && s[i+k] == s[j+k])
				k++;
			LCP[rank[i]] = k;
			if(k) k--;
		}
	}
	sufAr(string s)
	{
		n = s.size();
		pt.resize(n+1);
		cntSort.resize(n+1, -1);
		for(int i=0;i<n;i++) order.push_back(i);
		sort(order.begin(), order.end(), [&](int a, int b){
			return s[a] < s[b];
		});
		rank.resize(n);
		int cnt = 1;
		rank[order[0]] = cnt++;
		for(int i=1;i<n;i++)
			if(s[order[i]] == s[order[i-1]])
				rank[order[i]] = rank[order[i-1]];
			else
				rank[order[i]] = cnt++;
		layerCompute(1);
		lcpCnt(s);
//		debug(order);
//		debug(LCP);
	}
};
const int base = 1<<18;
struct segtree
{
	vector<int> tree;
	segtree()
	{
		tree.resize(base*2, -1);
	}
	void add(int w, int val)
	{
		w += base;
		tree[w] = val;
		w/=2;
		while(w != 0)
		{
			tree[w] = min(tree[w*2], tree[w*2+1]);
			w/=2;
		}
	}
	pair<int, int> bs(int w, int p, int k, int x, int val)
	{
		if(w >= base && tree[w] < val) return make_pair(-1, -1);
		if(tree[w] >= val) return {p, k};
		if(x < p)
			return bs(w*2, p, (p+k)/2, x, val);
		if(x > k)
			return bs(w*2+1, (p+k)/2+1, k, x, val);
		auto p1 = bs(w*2, p, (p+k)/2, x, val);
		auto p2 = bs(w*2+1, (p+k)/2+1, k, x, val);
		if(p2.first <= x && x <= p2.second) swap(p1, p2);
		if(p2 == make_pair(-1, -1)) return p1;
		if(p1 == make_pair(-1, -1)) return p1;
		assert(p1.first <= x && x <= p1.second);
		if(p2.second == p1.first - 1) p1.first = p2.first;
		if(p2.first == p1.second + 1) p1.second = p2.second;
		return p1;
	}
};
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);
	sufAr A(s);
	long long res = 0;
	segtree B;
	debug(A.LCP);
	for(int i=0;i<A.LCP.size();i++)
		B.add(i, A.LCP[i]);
	for(auto v : pals)
	{
		debug(v);
		int ans = 1;
		int r = A.rank[v.first];
		debug(r);
		auto p = B.bs(1, 0, base-1, r, v.second);
		debug(p);
		if(p.first != -1)
		ans = p.second - p.first + 2;
		else
		ans = 1;
		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 '__int128 hashTab::get(int, int, bool)':
palindrome.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<__int128>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   assert(x >= 0 && y < hs.size() && x <= y);
      |                    ~~^~~~~~~~~~~
palindrome.cpp: In lambda function:
palindrome.cpp:69:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   if(x + r >= s.size()) return false;
      |      ~~~~~~^~~~~~~~~~~
palindrome.cpp: In function 'int32_t main()':
palindrome.cpp:254:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  254 |  for(int i=0;i<A.LCP.size();i++)
      |              ~^~~~~~~~~~~~~

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