oj.uz

Submission #1116296

# Submission time Handle Problem Language Result Execution time Memory
1116296 2024-11-21T13:02:06 Z raczek Palindromes (APIO14_palindrome) C++17
73 / 100
 662 ms 89204 KB 
#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
#define __int128_t long long
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 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);
	}
};
struct rmq
{
	const int K = 18;
	const int base = 1<<K;
	int st[18][1<<19];
	int lg[(1<<18)+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)
	{
		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);
	sufAr A(s);
	long long res = 0;
	rmq B(A.LCP);
	debug(A.LCP.size());
	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)
	{
		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

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:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   assert(x >= 0 && y < hs.size() && x <= y);
      |                    ~~^~~~~~~~~~~
palindrome.cpp: In lambda function:
palindrome.cpp:71:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   if(x + r >= s.size()) return false;
      |      ~~~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 38192 KB Output is correct
2 Correct 35 ms 38216 KB Output is correct
3 Correct 32 ms 38216 KB Output is correct
4 Correct 33 ms 38224 KB Output is correct
5 Correct 32 ms 38376 KB Output is correct
6 Correct 34 ms 38216 KB Output is correct
7 Correct 31 ms 38236 KB Output is correct
8 Correct 34 ms 38164 KB Output is correct
9 Correct 41 ms 38232 KB Output is correct
10 Correct 33 ms 38172 KB Output is correct
11 Correct 35 ms 38396 KB Output is correct
12 Correct 32 ms 38236 KB Output is correct
13 Correct 31 ms 38376 KB Output is correct
14 Correct 32 ms 38224 KB Output is correct
15 Correct 45 ms 38296 KB Output is correct
16 Correct 33 ms 38224 KB Output is correct
17 Correct 34 ms 38216 KB Output is correct
18 Correct 36 ms 38216 KB Output is correct
19 Correct 42 ms 38224 KB Output is correct
20 Correct 32 ms 38216 KB Output is correct
21 Correct 32 ms 38224 KB Output is correct
22 Correct 31 ms 38224 KB Output is correct
23 Correct 31 ms 38312 KB Output is correct
24 Correct 36 ms 38224 KB Output is correct
25 Correct 35 ms 38404 KB Output is correct
26 Correct 34 ms 38216 KB Output is correct
27 Correct 43 ms 38216 KB Output is correct
28 Correct 45 ms 38216 KB Output is correct
29 Correct 32 ms 38224 KB Output is correct
30 Correct 35 ms 38224 KB Output is correct
31 Correct 45 ms 38216 KB Output is correct
32 Correct 35 ms 38216 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 38440 KB Output is correct
2 Correct 35 ms 38416 KB Output is correct
3 Correct 35 ms 38480 KB Output is correct
4 Correct 33 ms 38480 KB Output is correct
5 Correct 35 ms 38508 KB Output is correct
6 Correct 33 ms 38480 KB Output is correct
7 Correct 38 ms 38480 KB Output is correct
8 Correct 37 ms 38472 KB Output is correct
9 Correct 37 ms 38480 KB Output is correct
10 Correct 33 ms 38472 KB Output is correct
11 Correct 35 ms 38480 KB Output is correct
12 Correct 36 ms 38396 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 39496 KB Output is correct
2 Correct 47 ms 39760 KB Output is correct
3 Correct 43 ms 39760 KB Output is correct
4 Correct 44 ms 39760 KB Output is correct
5 Correct 51 ms 40032 KB Output is correct
6 Correct 48 ms 40016 KB Output is correct
7 Correct 44 ms 39616 KB Output is correct
8 Correct 41 ms 38984 KB Output is correct
9 Correct 42 ms 39004 KB Output is correct
10 Correct 44 ms 39752 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 50428 KB Output is correct
2 Correct 191 ms 52772 KB Output is correct
3 Correct 216 ms 52672 KB Output is correct
4 Correct 206 ms 52704 KB Output is correct
5 Correct 272 ms 55796 KB Output is correct
6 Correct 210 ms 52552 KB Output is correct
7 Correct 192 ms 51416 KB Output is correct
8 Correct 99 ms 45348 KB Output is correct
9 Correct 115 ms 46628 KB Output is correct
10 Correct 231 ms 53564 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 82048 KB Output is correct
2 Correct 630 ms 89204 KB Output is correct
3 Incorrect 662 ms 82300 KB Output isn't correct
4 Halted 0 ms 0 KB -