Submission #703248

#	Time	Username	Problem	Language	Result	Execution time	Memory
703248		600Mihnea	Palindromes (APIO14_palindrome)	C++17	100 / 100	89 ms	87552 KiB

palindrome

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

#define int long long

int dumb(string s)
{
	int n = (int)s.size();
	vector<vector<int>> lcp(n, vector<int>(n, 0));
	vector<vector<bool>> ispal(n, vector<bool>(n, 0));

	for (int i = 0; i < n; i++)
	{
		lcp[i][i] = n - i;
	}
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (s[i] == s[j])
			{
				int c = 0;
				if (i + 1 < n && j + 1 < n)
				{
					c += lcp[i + 1][j + 1];
				}
				lcp[i][j] = lcp[j][i] = 1 + c;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		ispal[i][i] = 1;
	}
	for (int i = 0; i + 1 < n; i++)
	{
		ispal[i][i + 1] = (s[i] == s[i + 1]);
	}
	for (int len = 3; len <= n; len++)
	{
		for (int i = 0; i + len - 1 < n; i++)
		{
			int j = i + len - 1;
			ispal[i][j] = ispal[i + 1][j - 1] & (s[i] == s[j]);
		}
	}
	int sol = 0;
	for (int len = 1; len <= n; len++)
	{
		for (int i = 0; i + len - 1 < n; i++)
		{
			int j = i + len - 1;
			if (ispal[i][j])
			{
				int matches = 0;
				for (int k = 0; k < n; k++)
				{
					matches += (lcp[k][i] >= len);
				}
				sol = max(sol, len * matches);
			}
		}
	}
	return sol;
}

struct Vertex
{
	int fail;
	int len;
	vector<int> kids;
	int cnt;
};

vector<Vertex> verts;
vector<int> mt(26, 0);

int smart(string s)
{
	verts.clear();
	verts.push_back({ 0, -1, mt, 0 });
	verts.push_back({ 0, 0,  mt, 0 });
	assert((int)s.size() >= 1);
	s = "$" + s;
	assert((int)s.size() >= 2);
	int n = (int)s.size();
	int curvert = 0;
	for (int i = 1; i < n; i++)
	{
		while (s[i] != s[i - verts[curvert].len - 1])
		{
			assert(curvert >= 1);
			curvert = verts[curvert].fail;
		}
		assert(s[i] == s[i - verts[curvert].len - 1]);
		
		{
			int x = s[i] - 'a';
			assert(0 <= x && x < 26);
			if (!verts[curvert].kids[x])
			{
				int fail = verts[curvert].fail;
				assert(fail >= 0);
				while (s[i] != s[i - verts[fail].len - 1])
				{
					assert(fail >= 1);
					fail = verts[fail].fail;
				}
				
				if (!verts[fail].kids[x])
				{
					assert(fail == 0);
					fail = 1;
				}
				else
				{
					fail = verts[fail].kids[x];
				}
			
				verts.push_back({ fail, verts[curvert].len + 2, mt, 0 });
				
				verts[curvert].kids[x] = (int)verts.size() - 1;
				//cout << (int)verts.size() - 1 << " -> " << fail << "\n";
			}
			curvert = verts[curvert].kids[x];
		}	
		verts[curvert].cnt++;
	}
	vector<int> q = { 0, 1 };
	for (int i = 0; i < (int)q.size(); i++)
	{
		int a = q[i];
		for (int x = 0; x < 26; x++)
		{
			if (verts[a].kids[x])
			{
				q.push_back(verts[a].kids[x]);
			}
		}
	}/*
	for (auto& x : q)
	{
		cout << x << " ";
	}
	cout << "\n";*/
	int sol = 0;
	for (int _ = (int)q.size() - 1; _ >= 0; _--)
	{
		int who = q[_];
		verts[verts[who].fail].cnt += verts[who].cnt;
		sol = max(sol, verts[who].len * verts[who].cnt);
	}
	return sol;
	exit(0);
}

mt19937 rng(228);

int getrng(int l, int r)
{
	assert(l <= r);
	int x = rng() % (r - l + 1) + l;
	assert(l <= x && x <= r);
	return x;
}

string gets(int dim)
{
	dim = getrng(1, dim);
	string s(dim, '?');
	for (auto& ch : s)
	{
		ch = 'a' + getrng(0, 4);
	}
	return s;
}

signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif


	string s;
	cin >> s;
	//cout << dumb(s) << "\n";
	cout << smart(s) << "\n";
	exit(0);
	if (0)
	{
		string s = "aaa";
		cout << smart(s) << "\n";
		cout << dumb(s) << "\n";
		exit(0);
	}

	while (1)
	{
		string s = gets(10);
		if (smart(s) != dumb(s))
		{
			cout << "bad : " << s << "\n";
			cout << "me    : " << smart(s) << "\n";
			cout << "good  : " << dumb(s) << "\n";
			exit(0);
		}
	}


	return 0;
}

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