답안 #211491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211491	2020-03-20T14:36:45 Z	Lawliet	Cubeword (CEOI19_cubeword)	C++17	100 / 100	487 ms	26628 KB

cubeword

#include <bits/stdc++.h>
 
using namespace std;
typedef long long int lli;
 
const int MAXS = 10;
const int MAXL = 65;
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 <= 'z' ) return a - 'a';
	if( 'A' <= a && a <= 'Z' ) return 'z' - 'a' + 1 + a - 'A';
	return 'z' - 'a' + 1 + 'Z' - 'A' + 1 +  a - '0';
}

int qtdPermutations()
{
	int ans = 24;
	int curFat = 1;
	int curNum = 1;

	for(int i = 1 ; i < 4 ; i++)
	{
		if( p[i] != p[i - 1] )
		{
			ans /= curFat;
			curNum = 0;
			curFat = 1;
		}

		curFat *= ++curNum;
	}

	ans /= curFat;

	return ans;
}
 
void backtracking(int i)
{
	if( i == 4 )
	{
		for(int sz = 3 ; sz <= 10 ; sz++)
		{
			lli t = qtdPermutations();
 
			t *= ans[ p[0] ][ p[1] ][ p[2] ][sz]; t %= MOD;
			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;
	}

	int lim = 0;
	if( !p.empty() ) lim = p.back();
 
	for(int k = lim ; k <= conv( '9' ) ; 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( '9' ) ; a++)
	{
		for(int b = a ; b <= conv( '9' ) ; b++)
		{
			for(int c = b ; c <= conv( '9' ) ; c++)
			{
				for(int sz = 3 ; sz <= 10 ; sz++)
				{
					for(int k = 0 ; k <= conv( '9' ) ; 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

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

Subtask #1
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	461 ms	25336 KB	Output is correct
2	Correct	473 ms	25336 KB	Output is correct
3	Correct	469 ms	25464 KB	Output is correct
4	Correct	459 ms	25336 KB	Output is correct
5	Correct	467 ms	25552 KB	Output is correct
6	Correct	468 ms	25336 KB	Output is correct
7	Correct	477 ms	25384 KB	Output is correct
8	Correct	468 ms	25464 KB	Output is correct
9	Correct	464 ms	25336 KB	Output is correct
10	Correct	472 ms	25336 KB	Output is correct
11	Correct	479 ms	25336 KB	Output is correct
12	Correct	470 ms	25336 KB	Output is correct
13	Correct	461 ms	25336 KB	Output is correct
14	Correct	468 ms	25608 KB	Output is correct
15	Correct	464 ms	25340 KB	Output is correct
16	Correct	468 ms	25336 KB	Output is correct
17	Correct	473 ms	25464 KB	Output is correct
18	Correct	480 ms	25336 KB	Output is correct
19	Correct	474 ms	25336 KB	Output is correct
20	Correct	485 ms	25336 KB	Output is correct
21	Correct	467 ms	25336 KB	Output is correct

Subtask #2
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	461 ms	25336 KB	Output is correct
2	Correct	473 ms	25336 KB	Output is correct
3	Correct	469 ms	25464 KB	Output is correct
4	Correct	459 ms	25336 KB	Output is correct
5	Correct	467 ms	25552 KB	Output is correct
6	Correct	468 ms	25336 KB	Output is correct
7	Correct	477 ms	25384 KB	Output is correct
8	Correct	468 ms	25464 KB	Output is correct
9	Correct	464 ms	25336 KB	Output is correct
10	Correct	472 ms	25336 KB	Output is correct
11	Correct	479 ms	25336 KB	Output is correct
12	Correct	470 ms	25336 KB	Output is correct
13	Correct	461 ms	25336 KB	Output is correct
14	Correct	468 ms	25608 KB	Output is correct
15	Correct	464 ms	25340 KB	Output is correct
16	Correct	468 ms	25336 KB	Output is correct
17	Correct	473 ms	25464 KB	Output is correct
18	Correct	480 ms	25336 KB	Output is correct
19	Correct	474 ms	25336 KB	Output is correct
20	Correct	485 ms	25336 KB	Output is correct
21	Correct	467 ms	25336 KB	Output is correct
22	Correct	478 ms	26104 KB	Output is correct
23	Correct	457 ms	25848 KB	Output is correct
24	Correct	469 ms	25976 KB	Output is correct
25	Correct	457 ms	25892 KB	Output is correct
26	Correct	479 ms	25992 KB	Output is correct
27	Correct	466 ms	26104 KB	Output is correct
28	Correct	460 ms	25928 KB	Output is correct
29	Correct	487 ms	26232 KB	Output is correct
30	Correct	460 ms	25848 KB	Output is correct
31	Correct	464 ms	26036 KB	Output is correct
32	Correct	463 ms	25848 KB	Output is correct
33	Correct	464 ms	25848 KB	Output is correct
34	Correct	462 ms	25976 KB	Output is correct
35	Correct	458 ms	25976 KB	Output is correct
36	Correct	457 ms	26104 KB	Output is correct
37	Correct	461 ms	25848 KB	Output is correct
38	Correct	468 ms	25848 KB	Output is correct
39	Correct	458 ms	25848 KB	Output is correct
40	Correct	467 ms	25848 KB	Output is correct
41	Correct	479 ms	25976 KB	Output is correct
42	Correct	458 ms	25976 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	461 ms	25336 KB	Output is correct
2	Correct	473 ms	25336 KB	Output is correct
3	Correct	469 ms	25464 KB	Output is correct
4	Correct	459 ms	25336 KB	Output is correct
5	Correct	467 ms	25552 KB	Output is correct
6	Correct	468 ms	25336 KB	Output is correct
7	Correct	477 ms	25384 KB	Output is correct
8	Correct	468 ms	25464 KB	Output is correct
9	Correct	464 ms	25336 KB	Output is correct
10	Correct	472 ms	25336 KB	Output is correct
11	Correct	479 ms	25336 KB	Output is correct
12	Correct	470 ms	25336 KB	Output is correct
13	Correct	461 ms	25336 KB	Output is correct
14	Correct	468 ms	25608 KB	Output is correct
15	Correct	464 ms	25340 KB	Output is correct
16	Correct	468 ms	25336 KB	Output is correct
17	Correct	473 ms	25464 KB	Output is correct
18	Correct	480 ms	25336 KB	Output is correct
19	Correct	474 ms	25336 KB	Output is correct
20	Correct	485 ms	25336 KB	Output is correct
21	Correct	467 ms	25336 KB	Output is correct
22	Correct	478 ms	26104 KB	Output is correct
23	Correct	457 ms	25848 KB	Output is correct
24	Correct	469 ms	25976 KB	Output is correct
25	Correct	457 ms	25892 KB	Output is correct
26	Correct	479 ms	25992 KB	Output is correct
27	Correct	466 ms	26104 KB	Output is correct
28	Correct	460 ms	25928 KB	Output is correct
29	Correct	487 ms	26232 KB	Output is correct
30	Correct	460 ms	25848 KB	Output is correct
31	Correct	464 ms	26036 KB	Output is correct
32	Correct	463 ms	25848 KB	Output is correct
33	Correct	464 ms	25848 KB	Output is correct
34	Correct	462 ms	25976 KB	Output is correct
35	Correct	458 ms	25976 KB	Output is correct
36	Correct	457 ms	26104 KB	Output is correct
37	Correct	461 ms	25848 KB	Output is correct
38	Correct	468 ms	25848 KB	Output is correct
39	Correct	458 ms	25848 KB	Output is correct
40	Correct	467 ms	25848 KB	Output is correct
41	Correct	479 ms	25976 KB	Output is correct
42	Correct	458 ms	25976 KB	Output is correct
43	Correct	467 ms	26236 KB	Output is correct
44	Correct	463 ms	26104 KB	Output is correct
45	Correct	474 ms	26392 KB	Output is correct
46	Correct	466 ms	26232 KB	Output is correct
47	Correct	461 ms	26104 KB	Output is correct
48	Correct	459 ms	26232 KB	Output is correct
49	Correct	449 ms	26104 KB	Output is correct
50	Correct	468 ms	26232 KB	Output is correct
51	Correct	456 ms	26104 KB	Output is correct
52	Correct	467 ms	26104 KB	Output is correct
53	Correct	457 ms	26232 KB	Output is correct
54	Correct	460 ms	26104 KB	Output is correct
55	Correct	469 ms	26360 KB	Output is correct
56	Correct	457 ms	26168 KB	Output is correct
57	Correct	461 ms	26352 KB	Output is correct
58	Correct	456 ms	26104 KB	Output is correct
59	Correct	458 ms	26232 KB	Output is correct
60	Correct	459 ms	26104 KB	Output is correct
61	Correct	477 ms	26104 KB	Output is correct
62	Correct	456 ms	26232 KB	Output is correct
63	Correct	450 ms	26104 KB	Output is correct

Subtask #4
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	461 ms	25336 KB	Output is correct
2	Correct	473 ms	25336 KB	Output is correct
3	Correct	469 ms	25464 KB	Output is correct
4	Correct	459 ms	25336 KB	Output is correct
5	Correct	467 ms	25552 KB	Output is correct
6	Correct	468 ms	25336 KB	Output is correct
7	Correct	477 ms	25384 KB	Output is correct
8	Correct	468 ms	25464 KB	Output is correct
9	Correct	464 ms	25336 KB	Output is correct
10	Correct	472 ms	25336 KB	Output is correct
11	Correct	479 ms	25336 KB	Output is correct
12	Correct	470 ms	25336 KB	Output is correct
13	Correct	461 ms	25336 KB	Output is correct
14	Correct	468 ms	25608 KB	Output is correct
15	Correct	464 ms	25340 KB	Output is correct
16	Correct	468 ms	25336 KB	Output is correct
17	Correct	473 ms	25464 KB	Output is correct
18	Correct	480 ms	25336 KB	Output is correct
19	Correct	474 ms	25336 KB	Output is correct
20	Correct	485 ms	25336 KB	Output is correct
21	Correct	467 ms	25336 KB	Output is correct
22	Correct	478 ms	26104 KB	Output is correct
23	Correct	457 ms	25848 KB	Output is correct
24	Correct	469 ms	25976 KB	Output is correct
25	Correct	457 ms	25892 KB	Output is correct
26	Correct	479 ms	25992 KB	Output is correct
27	Correct	466 ms	26104 KB	Output is correct
28	Correct	460 ms	25928 KB	Output is correct
29	Correct	487 ms	26232 KB	Output is correct
30	Correct	460 ms	25848 KB	Output is correct
31	Correct	464 ms	26036 KB	Output is correct
32	Correct	463 ms	25848 KB	Output is correct
33	Correct	464 ms	25848 KB	Output is correct
34	Correct	462 ms	25976 KB	Output is correct
35	Correct	458 ms	25976 KB	Output is correct
36	Correct	457 ms	26104 KB	Output is correct
37	Correct	461 ms	25848 KB	Output is correct
38	Correct	468 ms	25848 KB	Output is correct
39	Correct	458 ms	25848 KB	Output is correct
40	Correct	467 ms	25848 KB	Output is correct
41	Correct	479 ms	25976 KB	Output is correct
42	Correct	458 ms	25976 KB	Output is correct
43	Correct	467 ms	26236 KB	Output is correct
44	Correct	463 ms	26104 KB	Output is correct
45	Correct	474 ms	26392 KB	Output is correct
46	Correct	466 ms	26232 KB	Output is correct
47	Correct	461 ms	26104 KB	Output is correct
48	Correct	459 ms	26232 KB	Output is correct
49	Correct	449 ms	26104 KB	Output is correct
50	Correct	468 ms	26232 KB	Output is correct
51	Correct	456 ms	26104 KB	Output is correct
52	Correct	467 ms	26104 KB	Output is correct
53	Correct	457 ms	26232 KB	Output is correct
54	Correct	460 ms	26104 KB	Output is correct
55	Correct	469 ms	26360 KB	Output is correct
56	Correct	457 ms	26168 KB	Output is correct
57	Correct	461 ms	26352 KB	Output is correct
58	Correct	456 ms	26104 KB	Output is correct
59	Correct	458 ms	26232 KB	Output is correct
60	Correct	459 ms	26104 KB	Output is correct
61	Correct	477 ms	26104 KB	Output is correct
62	Correct	456 ms	26232 KB	Output is correct
63	Correct	450 ms	26104 KB	Output is correct
64	Correct	461 ms	26488 KB	Output is correct
65	Correct	453 ms	26488 KB	Output is correct
66	Correct	456 ms	26492 KB	Output is correct
67	Correct	466 ms	26616 KB	Output is correct
68	Correct	454 ms	26492 KB	Output is correct
69	Correct	462 ms	26628 KB	Output is correct
70	Correct	453 ms	26488 KB	Output is correct
71	Correct	466 ms	26616 KB	Output is correct
72	Correct	465 ms	26488 KB	Output is correct
73	Correct	463 ms	26488 KB	Output is correct
74	Correct	460 ms	26616 KB	Output is correct
75	Correct	455 ms	26488 KB	Output is correct
76	Correct	456 ms	26488 KB	Output is correct
77	Correct	480 ms	26492 KB	Output is correct
78	Correct	464 ms	26488 KB	Output is correct
79	Correct	458 ms	26488 KB	Output is correct
80	Correct	454 ms	26532 KB	Output is correct
81	Correct	467 ms	26516 KB	Output is correct
82	Correct	459 ms	26488 KB	Output is correct
83	Correct	456 ms	26616 KB	Output is correct
84	Correct	449 ms	26488 KB	Output is correct

답안 #211491

Compilation message

Subtask #1 21.0 / 21.0

Subtask #2 29.0 / 29.0

Subtask #3 34.0 / 34.0

Subtask #4 16.0 / 16.0

Subtask #1
21.0 / 21.0

Subtask #2
29.0 / 29.0

Subtask #3
34.0 / 34.0

Subtask #4
16.0 / 16.0