Submission #101359

#	Time	Username	Problem	Language	Result	Execution time	Memory
101359		ZwariowanyMarcin	Palindromes (APIO14_palindrome)	C++14	0 / 100	382 ms	11584 KiB

palindrome

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ss(v) (int)v.size()
#define fi first
#define se second
using namespace std;
const int nax = 2 * 300100;
char c[nax];
int kmr[nax];
pair < pair < int, int > , int > help[nax];
int gdzie[nax];
int lcp[nax];
stack < pair < int, int > > s;
int lewo[nax], prawo[nax];
int main()
{	
	scanf("%s", c + 1);
	int n = strlen(c + 1);
	ll ans = n;
	for(int i = 1; n >= i; ++i)
		kmr[i] = c[i];
	for(int j = 1; 1000 > j; ++j)
		{
			for(int i = 1; n >= i; ++i)
				help[i] = {{kmr[i], kmr[i + (1 << (j - 1))]}, i};
			sort(help + 1, help + n + 1);
			int cnt = 1;
			for(int i = 1; n >= i; ++i)
				{
					kmr[help[i].se] = cnt;
					if(help[i].fi != help[i + 1].fi)
						cnt++;
				}
			if(cnt == n + 1)
				break;
		}
	for(int i = 1; n >= i; ++i)
		gdzie[kmr[i]] = i;
	int k = 0;
	for(int i = 1; n >= i; ++i)
		{
			while(c[i + k] == c[gdzie[kmr[i] + 1] + k])
				k++;
			lcp[kmr[i]] = k;
			if(k)
				--k;
		}
	for(int i = 1; n >= i; ++i)
		lewo[i] = prawo[i] = i;
	for(int i = 1; n >= i; ++i)
	{
		while(!s.empty() && s.top().first > lcp[i])
			{
				prawo[s.top().second] = i;
				s.pop();
			}
		s.push({lcp[i], i});
	}
	while(!s.empty())
		s.pop();
	for(int i = n; i >= 1; --i)
	{
		while(!s.empty() && s.top().first > lcp[i])
			{
				lewo[s.top().second] = i + 1;
				s.pop();
			}
		s.push({lcp[i], i});
	}
	while(!s.empty())
		{
			lewo[s.top().se] = 1;
			s.pop();
		}
	for(int i = 1; n >= i; ++i)
		ans = max(ans, (ll)(lcp[i] * (prawo[i] - lewo[i] + 1)));
	printf("%lld", ans);
	
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", c + 1);
  ~~~~~^~~~~~~~~~~~~

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