Submission #199995

#	Time	Username	Problem	Language	Result	Execution time	Memory
199995		davitmarg	Cubeword (CEOI19_cubeword)	C++17	84 / 100	1167 ms	30280 KiB

cubeword

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
 
 
LL ml(LL a,LL b)
{
	return (a*b)%mod;
}
 
int N;
 
int n;
string s;
vector<string> str;
vector<char> chars;
char id;
map<char,char> newchar;
map<string,bool> used;
 
LL p[12][70][70],dp[12][70][70][70],ans;
 
int main()
{
	cin>>n;
	while(n--)
	{
		cin>>s;
		str.PB(s);
		while(!s.empty())
		{
			chars.PB(s.back());
			s.pop_back();	
		}
	}
 
 
	id=0;
	sort(all(chars));
	for(int i=0;i<chars.size();i++)
		if(!i || chars[i]!=chars[i-1])
			newchar[chars[i]]=id++;
 
	N=id;
	id--;
 
	while(!str.empty())
	{
		s=str.back();
		str.pop_back();
		for(int i=0;i<s.size();i++)
			s[i]=newchar[s[i]];
		
		if(!used[s])
		{
			p[s.length()][s[0]][s.back()]++;
			used[s]=1;
		}
		reverse(all(s));
		if(!used[s])
		{
			p[s.length()][s[0]][s.back()]++;
			used[s]=1;
		}
	}
 
	for(int len=1;len<=10;len++)
	{
		for(int i=0;i<N;i++)
			for(int a=0;a<N;a++)
				for(int b=0;b<N;b++)
					for(int c=0;c<N;c++)
					{
						dp[len][a][b][c]+=ml(p[len][i][a],ml(p[len][i][b],p[len][i][c]));
						dp[len][a][b][c]%=mod;
					}
 
		for(int a=0;a<N;a++)
			for(int b=0;b<N;b++)
				for(int c=0;c<N;c++)
					for(int d=0;d<N;d++)
					{
						ans+=ml(dp[len][a][b][c],ml(dp[len][a][b][d],ml(dp[len][a][d][c],dp[len][d][b][c])));
						ans%=mod;
					}
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'int main()':
cubeword.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<chars.size();i++)
              ~^~~~~~~~~~~~~
cubeword.cpp:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.size();i++)
               ~^~~~~~~~~
cubeword.cpp:76:22: warning: array subscript has type 'char' [-Wchar-subscripts]
    p[s.length()][s[0]][s.back()]++;
                      ^
cubeword.cpp:76:32: warning: array subscript has type 'char' [-Wchar-subscripts]
    p[s.length()][s[0]][s.back()]++;
                                ^
cubeword.cpp:82:22: warning: array subscript has type 'char' [-Wchar-subscripts]
    p[s.length()][s[0]][s.back()]++;
                      ^
cubeword.cpp:82:32: warning: array subscript has type 'char' [-Wchar-subscripts]
    p[s.length()][s[0]][s.back()]++;
                                ^

• Subtask 1: 21 / 21
• Subtask 2: 29 / 29
• Subtask 3: 34 / 34
• Subtask 4: 0 / 16