답안 #241632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241632	2020-06-24T21:22:45 Z	luciocf	Cubeword (CEOI19_cubeword)	C++14	100 / 100	530 ms	22392 KB

cubeword

// CEOI 2019 - Cubeword
// Lúcio Cardoso

// Solution is the same as in editorial in CF

#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;

const int maxn = 62;
const int mod = 998244353;

int cnt[8][maxn][maxn];
int qtd[8][maxn][maxn][maxn];

inline int get(char c)
{
	if (c >= 'a' && c <= 'z') return (int)(c-'a');
	if (c >= 'A' && c <= 'Z') return (int)(c-'A')+26;
	return (int)(c-'0')+52;
}

int main(void)
{
	int n;
	scanf("%d", &n);

	map<string, bool> mark;

	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;

		if (!mark[s])
			cnt[s.size()-3][get(s[0])][get(s.back())]++;

		mark[s] = true;

		reverse(s.begin(), s.end());

		if (!mark[s])
			cnt[s.size()-3][get(s[0])][get(s.back())]++;

		mark[s] = true;
	}

	for (int sz = 0; sz < 8; sz++)
		for (int a = 0; a < 62; a++)
			for (int b = a; b < 62; b++)
				for (int c = b; c < 62; c++)
					for (int d = 0; d < 62; d++)
						qtd[sz][a][b][c] = (1ll*qtd[sz][a][b][c] + 1ll*cnt[sz][d][a]*cnt[sz][d][b]*cnt[sz][d][c])%mod;

	int ans = 0;

	for (int sz = 0; sz < 8; sz++)
	{
		for (int a = 0; a < 62; a++)
		{
			for (int b = a; b < 62; b++)
			{
				for (int c = b; c < 62; c++)
				{
					for (int d = c; d < 62; d++)
					{
						int p1 = (1ll*qtd[sz][a][c][d]*qtd[sz][b][c][d])%mod;
						int p2 = (1ll*qtd[sz][a][b][d]*qtd[sz][a][b][c])%mod;

						int k = (1ll*p1*p2)%mod, mult = 24;

						if (a == b && b == c && c == d) mult /= 24;
						else if (a == b && b == c) mult /= 6;
						else if (a == b)
						{
							mult /= 2;
							if (c == d) mult /= 2;
						}
						else
						{
							if (b == c && c == d) mult /= 6;
							else if (b == c) mult /= 2;
							else if (c == d) mult /= 2;
						}

						ans = (ans + (1ll*mult*k)%mod)%mod;
					}
				}
			}
		}
	}

	printf("%d\n", ans);
}

Compilation message

cubeword.cpp:10:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
cubeword.cpp: In function 'int main()':
cubeword.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~

Subtask #1
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	474 ms	21240 KB	Output is correct
2	Correct	497 ms	21196 KB	Output is correct
3	Correct	463 ms	21244 KB	Output is correct
4	Correct	463 ms	21240 KB	Output is correct
5	Correct	483 ms	21116 KB	Output is correct
6	Correct	488 ms	21276 KB	Output is correct
7	Correct	466 ms	21240 KB	Output is correct
8	Correct	486 ms	21240 KB	Output is correct
9	Correct	498 ms	21348 KB	Output is correct
10	Correct	478 ms	21172 KB	Output is correct
11	Correct	467 ms	21216 KB	Output is correct
12	Correct	478 ms	21240 KB	Output is correct
13	Correct	489 ms	21400 KB	Output is correct
14	Correct	467 ms	21292 KB	Output is correct
15	Correct	462 ms	21112 KB	Output is correct
16	Correct	473 ms	21240 KB	Output is correct
17	Correct	482 ms	21368 KB	Output is correct
18	Correct	506 ms	21112 KB	Output is correct
19	Correct	507 ms	21240 KB	Output is correct
20	Correct	497 ms	21068 KB	Output is correct
21	Correct	468 ms	21112 KB	Output is correct

Subtask #2
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	474 ms	21240 KB	Output is correct
2	Correct	497 ms	21196 KB	Output is correct
3	Correct	463 ms	21244 KB	Output is correct
4	Correct	463 ms	21240 KB	Output is correct
5	Correct	483 ms	21116 KB	Output is correct
6	Correct	488 ms	21276 KB	Output is correct
7	Correct	466 ms	21240 KB	Output is correct
8	Correct	486 ms	21240 KB	Output is correct
9	Correct	498 ms	21348 KB	Output is correct
10	Correct	478 ms	21172 KB	Output is correct
11	Correct	467 ms	21216 KB	Output is correct
12	Correct	478 ms	21240 KB	Output is correct
13	Correct	489 ms	21400 KB	Output is correct
14	Correct	467 ms	21292 KB	Output is correct
15	Correct	462 ms	21112 KB	Output is correct
16	Correct	473 ms	21240 KB	Output is correct
17	Correct	482 ms	21368 KB	Output is correct
18	Correct	506 ms	21112 KB	Output is correct
19	Correct	507 ms	21240 KB	Output is correct
20	Correct	497 ms	21068 KB	Output is correct
21	Correct	468 ms	21112 KB	Output is correct
22	Correct	462 ms	21728 KB	Output is correct
23	Correct	477 ms	21880 KB	Output is correct
24	Correct	452 ms	21880 KB	Output is correct
25	Correct	464 ms	21752 KB	Output is correct
26	Correct	465 ms	21752 KB	Output is correct
27	Correct	465 ms	21880 KB	Output is correct
28	Correct	456 ms	21752 KB	Output is correct
29	Correct	461 ms	21772 KB	Output is correct
30	Correct	468 ms	22008 KB	Output is correct
31	Correct	447 ms	21752 KB	Output is correct
32	Correct	492 ms	21752 KB	Output is correct
33	Correct	471 ms	21880 KB	Output is correct
34	Correct	480 ms	21752 KB	Output is correct
35	Correct	458 ms	21752 KB	Output is correct
36	Correct	456 ms	21880 KB	Output is correct
37	Correct	486 ms	21752 KB	Output is correct
38	Correct	457 ms	21752 KB	Output is correct
39	Correct	464 ms	21752 KB	Output is correct
40	Correct	491 ms	21752 KB	Output is correct
41	Correct	474 ms	21752 KB	Output is correct
42	Correct	470 ms	21752 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	474 ms	21240 KB	Output is correct
2	Correct	497 ms	21196 KB	Output is correct
3	Correct	463 ms	21244 KB	Output is correct
4	Correct	463 ms	21240 KB	Output is correct
5	Correct	483 ms	21116 KB	Output is correct
6	Correct	488 ms	21276 KB	Output is correct
7	Correct	466 ms	21240 KB	Output is correct
8	Correct	486 ms	21240 KB	Output is correct
9	Correct	498 ms	21348 KB	Output is correct
10	Correct	478 ms	21172 KB	Output is correct
11	Correct	467 ms	21216 KB	Output is correct
12	Correct	478 ms	21240 KB	Output is correct
13	Correct	489 ms	21400 KB	Output is correct
14	Correct	467 ms	21292 KB	Output is correct
15	Correct	462 ms	21112 KB	Output is correct
16	Correct	473 ms	21240 KB	Output is correct
17	Correct	482 ms	21368 KB	Output is correct
18	Correct	506 ms	21112 KB	Output is correct
19	Correct	507 ms	21240 KB	Output is correct
20	Correct	497 ms	21068 KB	Output is correct
21	Correct	468 ms	21112 KB	Output is correct
22	Correct	462 ms	21728 KB	Output is correct
23	Correct	477 ms	21880 KB	Output is correct
24	Correct	452 ms	21880 KB	Output is correct
25	Correct	464 ms	21752 KB	Output is correct
26	Correct	465 ms	21752 KB	Output is correct
27	Correct	465 ms	21880 KB	Output is correct
28	Correct	456 ms	21752 KB	Output is correct
29	Correct	461 ms	21772 KB	Output is correct
30	Correct	468 ms	22008 KB	Output is correct
31	Correct	447 ms	21752 KB	Output is correct
32	Correct	492 ms	21752 KB	Output is correct
33	Correct	471 ms	21880 KB	Output is correct
34	Correct	480 ms	21752 KB	Output is correct
35	Correct	458 ms	21752 KB	Output is correct
36	Correct	456 ms	21880 KB	Output is correct
37	Correct	486 ms	21752 KB	Output is correct
38	Correct	457 ms	21752 KB	Output is correct
39	Correct	464 ms	21752 KB	Output is correct
40	Correct	491 ms	21752 KB	Output is correct
41	Correct	474 ms	21752 KB	Output is correct
42	Correct	470 ms	21752 KB	Output is correct
43	Correct	462 ms	22020 KB	Output is correct
44	Correct	504 ms	22224 KB	Output is correct
45	Correct	498 ms	22008 KB	Output is correct
46	Correct	466 ms	21880 KB	Output is correct
47	Correct	467 ms	22140 KB	Output is correct
48	Correct	465 ms	22008 KB	Output is correct
49	Correct	452 ms	21932 KB	Output is correct
50	Correct	458 ms	22112 KB	Output is correct
51	Correct	503 ms	22108 KB	Output is correct
52	Correct	456 ms	22008 KB	Output is correct
53	Correct	530 ms	22052 KB	Output is correct
54	Correct	495 ms	22136 KB	Output is correct
55	Correct	460 ms	22392 KB	Output is correct
56	Correct	463 ms	22016 KB	Output is correct
57	Correct	466 ms	21880 KB	Output is correct
58	Correct	439 ms	21880 KB	Output is correct
59	Correct	480 ms	21964 KB	Output is correct
60	Correct	461 ms	22008 KB	Output is correct
61	Correct	456 ms	22008 KB	Output is correct
62	Correct	457 ms	22008 KB	Output is correct
63	Correct	487 ms	21896 KB	Output is correct

Subtask #4
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	474 ms	21240 KB	Output is correct
2	Correct	497 ms	21196 KB	Output is correct
3	Correct	463 ms	21244 KB	Output is correct
4	Correct	463 ms	21240 KB	Output is correct
5	Correct	483 ms	21116 KB	Output is correct
6	Correct	488 ms	21276 KB	Output is correct
7	Correct	466 ms	21240 KB	Output is correct
8	Correct	486 ms	21240 KB	Output is correct
9	Correct	498 ms	21348 KB	Output is correct
10	Correct	478 ms	21172 KB	Output is correct
11	Correct	467 ms	21216 KB	Output is correct
12	Correct	478 ms	21240 KB	Output is correct
13	Correct	489 ms	21400 KB	Output is correct
14	Correct	467 ms	21292 KB	Output is correct
15	Correct	462 ms	21112 KB	Output is correct
16	Correct	473 ms	21240 KB	Output is correct
17	Correct	482 ms	21368 KB	Output is correct
18	Correct	506 ms	21112 KB	Output is correct
19	Correct	507 ms	21240 KB	Output is correct
20	Correct	497 ms	21068 KB	Output is correct
21	Correct	468 ms	21112 KB	Output is correct
22	Correct	462 ms	21728 KB	Output is correct
23	Correct	477 ms	21880 KB	Output is correct
24	Correct	452 ms	21880 KB	Output is correct
25	Correct	464 ms	21752 KB	Output is correct
26	Correct	465 ms	21752 KB	Output is correct
27	Correct	465 ms	21880 KB	Output is correct
28	Correct	456 ms	21752 KB	Output is correct
29	Correct	461 ms	21772 KB	Output is correct
30	Correct	468 ms	22008 KB	Output is correct
31	Correct	447 ms	21752 KB	Output is correct
32	Correct	492 ms	21752 KB	Output is correct
33	Correct	471 ms	21880 KB	Output is correct
34	Correct	480 ms	21752 KB	Output is correct
35	Correct	458 ms	21752 KB	Output is correct
36	Correct	456 ms	21880 KB	Output is correct
37	Correct	486 ms	21752 KB	Output is correct
38	Correct	457 ms	21752 KB	Output is correct
39	Correct	464 ms	21752 KB	Output is correct
40	Correct	491 ms	21752 KB	Output is correct
41	Correct	474 ms	21752 KB	Output is correct
42	Correct	470 ms	21752 KB	Output is correct
43	Correct	462 ms	22020 KB	Output is correct
44	Correct	504 ms	22224 KB	Output is correct
45	Correct	498 ms	22008 KB	Output is correct
46	Correct	466 ms	21880 KB	Output is correct
47	Correct	467 ms	22140 KB	Output is correct
48	Correct	465 ms	22008 KB	Output is correct
49	Correct	452 ms	21932 KB	Output is correct
50	Correct	458 ms	22112 KB	Output is correct
51	Correct	503 ms	22108 KB	Output is correct
52	Correct	456 ms	22008 KB	Output is correct
53	Correct	530 ms	22052 KB	Output is correct
54	Correct	495 ms	22136 KB	Output is correct
55	Correct	460 ms	22392 KB	Output is correct
56	Correct	463 ms	22016 KB	Output is correct
57	Correct	466 ms	21880 KB	Output is correct
58	Correct	439 ms	21880 KB	Output is correct
59	Correct	480 ms	21964 KB	Output is correct
60	Correct	461 ms	22008 KB	Output is correct
61	Correct	456 ms	22008 KB	Output is correct
62	Correct	457 ms	22008 KB	Output is correct
63	Correct	487 ms	21896 KB	Output is correct
64	Correct	453 ms	22392 KB	Output is correct
65	Correct	466 ms	22240 KB	Output is correct
66	Correct	460 ms	22324 KB	Output is correct
67	Correct	461 ms	22264 KB	Output is correct
68	Correct	455 ms	22136 KB	Output is correct
69	Correct	452 ms	22136 KB	Output is correct
70	Correct	457 ms	22272 KB	Output is correct
71	Correct	446 ms	22264 KB	Output is correct
72	Correct	447 ms	22264 KB	Output is correct
73	Correct	446 ms	22220 KB	Output is correct
74	Correct	470 ms	22392 KB	Output is correct
75	Correct	445 ms	22264 KB	Output is correct
76	Correct	479 ms	22264 KB	Output is correct
77	Correct	441 ms	22264 KB	Output is correct
78	Correct	450 ms	22264 KB	Output is correct
79	Correct	464 ms	22268 KB	Output is correct
80	Correct	452 ms	22260 KB	Output is correct
81	Correct	463 ms	22324 KB	Output is correct
82	Correct	444 ms	22136 KB	Output is correct
83	Correct	450 ms	22392 KB	Output is correct
84	Correct	443 ms	22264 KB	Output is correct

답안 #241632

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