oj.uz

Submission #375013

# Submission time Handle Problem Language Result Execution time Memory
375013 2021-03-08T21:03:30 Z ogibogi2004 Cubeword (CEOI19_cubeword) C++14
0 / 100
 1100 ms 11244 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e5+6;
map<char,int>mp;
const ll mod=998244353;
string s[MAXN];
int cnt[100][100];
int ans=0,n;
int dp[100][100][100];
void solve(int d)
{
	memset(cnt,0,sizeof(cnt));
	memset(dp,0,sizeof(dp));
	set<string>used;
	for(int i=0;i<n;i++)
	{
		if(s[i].size()!=d)continue;
		if(used.find(s[i])==used.end())
		{
			used.insert(s[i]);
			cnt[mp[s[i][0]]][mp[s[i][s[i].size()-1]]]++;
		}
		reverse(s[i].begin(),s[i].end());
		if(used.find(s[i])==used.end())
		{
			used.insert(s[i]);
			cnt[mp[s[i][0]]][mp[s[i][s[i].size()-1]]]++;
		}
		reverse(s[i].begin(),s[i].end());
	}
	if(used.size()==0)return;
	//cout<<d<<endl;
	for(int i1=1;i1<=62;i1++)
	{
		for(int i2=1;i2<=62;i2++)
		{
			for(int i3=1;i3<=62;i3++)
			{
				for(int j=1;j<=62;j++)
				{
					dp[i1][i2][i3]=dp[i1][i2][i3]+((ll)((ll)cnt[j][i1]*cnt[j][i2])%mod*cnt[j][i3])%mod;
					dp[i1][i2][i3]%=mod;
				}
			}
		}
	}
	for(int i1=1;i1<=62;i1++)
	{
		for(int i2=1;i2<=62;i2++)
		{
			for(int i3=1;i3<=62;i3++)
			{
				for(int i4=1;i4<=62;i4++)
				{
					ans=ans+((ll)(((ll)(((ll)dp[i1][i2][i3]*dp[i1][i2][i4])%mod)*dp[i1][i3][i4])%mod)*dp[i2][i3][i4])%mod;
					ans%=mod;
				}
			}
		}
	}
}
int main()
{
	for(char c='a';c<='z';c++)mp[c]=c-'a'+1;
	for(char c='A';c<='Z';c++)mp[c]=c-'A'+27;
	for(char c='0';c<='9';c++)mp[c]=c-'a'+43;
	cin>>n;
	for(int i=0;i<n;i++)cin>>s[i];
	for(int i=3;i<=10;i++)
	{
		solve(i);
	}
	cout<<ans<<endl;
return 0;
}

Compilation message

cubeword.cpp: In function 'void solve(int)':
cubeword.cpp:18:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |   if(s[i].size()!=d)continue;
      |      ~~~~~~~~~~~^~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1190 ms 11244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1190 ms 11244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1190 ms 11244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1190 ms 11244 KB Time limit exceeded
2 Halted 0 ms 0 KB -