Submission #210852

#	Time	Username	Problem	Language	Result	Execution time	Memory
210852		Lawliet	Cubeword (CEOI19_cubeword)	C++17	84 / 100	667 ms	32888 KiB

cubeword

#include <bits/stdc++.h>
 
using namespace std;
typedef long long int lli;
 
const int MAXS = 10;
const int MAXL = 35;
const int MAXN = 100010;
const int MOD = 998244353;
 
int n;
 
int qtd[MAXL][MAXL][MAXS];
 
lli ans[MAXL][MAXL][MAXL][MAXS];
 
lli result;
 
vector< int > p;
 
set< string > s;
 
int conv(char a)
{
	if( 'a' <= a && a <= 'p' ) return a - 'a';
	return 'p' - 'a' + 1 + a - 'A';
}
 
void backtracking(int i)
{
	if( i == 4 )
	{
		for(int sz = 3 ; sz <= 10 ; sz++)
		{
			lli t = 1;
 
			t *= ans[ p[0] ][ p[1] ][ p[2] ][sz];
			t *= ans[ p[0] ][ p[1] ][ p[3] ][sz]; t %= MOD;
			t *= ans[ p[0] ][ p[2] ][ p[3] ][sz]; t %= MOD;
			t *= ans[ p[1] ][ p[2] ][ p[3] ][sz]; t %= MOD;
 
			result += t;
			result %= MOD;
		}
 
		return;
	}
 
	for(int k = 0 ; k <= conv( 'P' ) ; k++)
	{
		p.push_back( k );
		backtracking( i + 1 );
		p.pop_back();
	}
}
 
int main()
{
	cin >> n;
 
	for(int i = 1 ; i <= n ; i++)
	{
		string t;
		cin >> t;
 
		s.insert( t );
		reverse( t.begin() , t.end() );
		s.insert( t );
	}
 
	for(auto it = s.begin() ; it != s.end() ; it++)
	{
		string curT = *it;
 
		int first = conv( curT[0] );
		int last = conv( curT.back() );
		int sz = curT.size();
 
		qtd[first][last][sz]++;
	}
 
	for(int a = 0 ; a <= conv( 'P' ) ; a++)
	{
		for(int b = 0 ; b <= conv( 'P' ) ; b++)
		{
			for(int c = 0 ; c <= conv( 'P' ) ; c++)
			{
				for(int sz = 3 ; sz <= 10 ; sz++)
				{
					for(int k = 0 ; k <= conv( 'P' ) ; k++)
					{
						lli aux = 1;
 
						aux *= qtd[a][k][sz];
						aux *= qtd[b][k][sz];
						aux *= qtd[c][k][sz];
 
						ans[a][b][c][sz] += aux;
						ans[a][b][c][sz] %= MOD;
					}
				}
			}
		}
	}
 
	backtracking( 0 );
 
	printf("%lld\n",result);
}

Compilation message (stderr)

cubeword.cpp: In function 'void backtracking(int)':
cubeword.cpp:37:6: warning: iteration 7 invokes undefined behavior [-Waggressive-loop-optimizations]
    t *= ans[ p[0] ][ p[1] ][ p[2] ][sz];
    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cubeword.cpp:33:23: note: within this loop
   for(int sz = 3 ; sz <= 10 ; sz++)
                    ~~~^~~~~

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