Submission #997369

#	Time	Username	Problem	Language	Result	Execution time	Memory
997369		vjudge1	Palindromes (APIO14_palindrome)	C++17	23 / 100	1046 ms	11104 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL),cout.tie(NULL);
	
	string s;
	cin>>s;
	int n=s.size();
	vector<int> ind[n];
	bool vis1[n]={};
	int ans=0;
	for (int i=0;i<n;i++)
	{
		if (vis1[i])
			continue;
		for (int j=i;j<n;j++)
			if (s[i]==s[j])
				ind[i].push_back(j),vis1[j]=true;
		if (ans<ind[i].size())
			ans=ind[i].size();
	}
	for (int sz=1;sz<n;sz++)
	{
		bool vis[n]={};
		for (int i=0;i<n;i++)
		{
			if (vis[i] or ind[i].empty())
				continue;
			vector<int> ind1[26];
			for (int j:ind[i])
			{
				vis[j]=true;
				if (j<sz or j+sz>=n or s[j-sz]!=s[j+sz])
					continue;
				ind1[s[j-sz]-'a'].push_back(j);
			}
			vector<int> v;
			for (int j:ind[i])
			{
				if (j<sz or j+sz>=n or s[j-sz]!=s[j+sz])
					continue;
				if (ind1[s[j-sz]-'a'][0]==i)
					v=ind1[s[j-sz]-'a'];
				else
					ind[ind1[s[j-sz]-'a'][0]]=ind1[s[j-sz]-'a'];
			}
			ind[i]=v;
		}
		for (int i=0;i<n;i++)
			if (ans<ind[i].size()*(2*sz+1))
				ans=ind[i].size()*(2*sz+1);
	}
	for (int i=0;i<n;i++)
		vis1[i]=0,ind[i].clear();
	for (int i=0;i<n-1;i++)
	{
		if (vis1[i] or s[i]!=s[i+1])
			continue;
		for (int j=i;j<n-1;j++)
			if (s[i]==s[j] and s[j]==s[j+1])
				ind[i].push_back(j),vis1[j]=true;
		if (ans<ind[i].size()*2)
			ans=ind[i].size()*2;
	}
	for (int sz=1;sz<n;sz++)
	{
		bool vis[n]={};
		for (int i=0;i<n;i++)
		{
			if (vis[i] or ind[i].empty())
				continue;
			vector<int> ind1[26];
			for (int j:ind[i])
			{
				vis[j]=true;
				if (j<sz or j+sz+1>=n or s[j-sz]!=s[j+sz+1])
					continue;
				ind1[s[j-sz]-'a'].push_back(j);
			}
			vector<int> v;
			for (int j:ind[i])
			{
				if (j<sz or j+sz+1>=n or s[j-sz]!=s[j+sz+1])
					continue;
				if (ind1[s[j-sz]-'a'][0]==i)
					v=ind1[s[j-sz]-'a'];
				else if(ind1[s[j-sz]-'a'][0]==j)
					ind[j]=ind1[s[j-sz]-'a'];
			}
			ind[i]=v;
		}
		for (int i=0;i<n;i++)
			if (ans<ind[i].size()*(sz*2+2))
				ans=(sz*2+2)*(int)ind[i].size();
	}
	cout<<ans<<endl;

	return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:23:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   if (ans<ind[i].size())
      |       ~~~^~~~~~~~~~~~~~
palindrome.cpp:54:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    if (ans<ind[i].size()*(2*sz+1))
      |        ~~~^~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:66:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   if (ans<ind[i].size()*2)
      |       ~~~^~~~~~~~~~~~~~~~
palindrome.cpp:97:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |    if (ans<ind[i].size()*(sz*2+2))
      |        ~~~^~~~~~~~~~~~~~~~~~~~~~~

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