oj.uz

Submission #101359

# Submission time Handle Problem Language Result Execution time Memory
101359 2019-03-18T17:20:20 Z ZwariowanyMarcin Palindromes (APIO14_palindrome) C++14
0 / 100
 382 ms 11584 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 4184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 382 ms 11584 KB Output isn't correct
2 Halted 0 ms 0 KB -