oj.uz

Submission #207917

# Submission time Handle Problem Language Result Execution time Memory
207917 2020-03-09T12:18:06 Z E869120 Cubeword (CEOI19_cubeword) C++14
50 / 100
 358 ms 13284 KB 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

const long long mod = 998244353;
const int MAX_VAL = 32;

int N; string S[1 << 18];
char c[10009];

int cnt[62][62];
long long ret[62][62][62];

int getc(char d) {
	if ('a' <= d && d <= 'z') return (d - 'a');
	if ('A' <= d && d <= 'Z') return (d - 'A') + 26;
	return (d - '0') + 52;
}

long long getcnt(int v1, int v2) {
	return cnt[v1][v2];
}

long long solve(int pos) {
	for (int i = 0; i < 62 * 62; i++) cnt[i / 62][i % 62] = 0;

	vector<string> vec;
	for (int i = 1; i <= N; i++) {
		if (S[i].size() != pos) continue;
		string T = S[i]; reverse(T.begin(), T.end());
		vec.push_back(S[i]);
		vec.push_back(T);
	}
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());

	for (string i : vec) {
		int c1 = getc(i[0]), c2 = getc(i[i.size() - 1]);
		cnt[c1][c2] += 1;
	}

	for (int i = 0; i < MAX_VAL; i++) {
		for (int j = i; j < MAX_VAL; j++) {
			for (int k = j; k < MAX_VAL; k++) {
				ret[i][j][k] = 0;
				for (int l = 0; l < MAX_VAL; l++) {
					ret[i][j][k] += getcnt(i, l) * getcnt(j, l) * getcnt(k, l);
					ret[i][j][k] %= mod;
				}
			}
		}
	}

	long long val = 0;
	for (int i = 0; i < MAX_VAL; i++) {
		for (int j = 0; j < MAX_VAL; j++) {
			for (int k = 0; k < MAX_VAL; k++) {
				for (int l = 0; l < MAX_VAL; l++) {
					int c[4] = { i, j, k, l };
					sort(c, c + 4);
					int A = c[0], B = c[1], C = c[2], D = c[3];
					val += (ret[A][B][C] * ret[A][B][D] % mod) * (ret[A][C][D] * ret[B][C][D] % mod);
					val %= mod;
				}
			}
		}
	}
	return val;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 11; j++) c[j] = 0;
		scanf("%s", &c);
		for (int j = 0; j < 11; j++) { if (c[j] == 0) break; S[i] += c[j]; }
	}

	long long ans = 0;
	for (int i = 3; i <= 10; i++) {
		ans += solve(i);
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}

Compilation message

cubeword.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
cubeword.cpp: In function 'long long int solve(int)':
cubeword.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (S[i].size() != pos) continue;
       ~~~~~~~~~~~~^~~~~~
cubeword.cpp: In function 'int main()':
cubeword.cpp:78:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[10009]' [-Wformat=]
   scanf("%s", &c);
               ~~^
cubeword.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &c);
   ~~~~~^~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 12192 KB Output is correct
2 Correct 342 ms 13164 KB Output is correct
3 Correct 342 ms 13092 KB Output is correct
4 Correct 344 ms 13032 KB Output is correct
5 Correct 348 ms 13032 KB Output is correct
6 Correct 348 ms 13148 KB Output is correct
7 Correct 342 ms 13048 KB Output is correct
8 Correct 346 ms 13032 KB Output is correct
9 Correct 355 ms 13028 KB Output is correct
10 Correct 346 ms 13024 KB Output is correct
11 Correct 343 ms 13284 KB Output is correct
12 Correct 340 ms 13028 KB Output is correct
13 Correct 345 ms 13040 KB Output is correct
14 Correct 342 ms 13036 KB Output is correct
15 Correct 338 ms 13144 KB Output is correct
16 Correct 346 ms 13032 KB Output is correct
17 Correct 358 ms 13032 KB Output is correct
18 Correct 350 ms 13132 KB Output is correct
19 Correct 343 ms 13060 KB Output is correct
20 Correct 352 ms 13084 KB Output is correct
21 Correct 345 ms 13136 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 12192 KB Output is correct
2 Correct 342 ms 13164 KB Output is correct
3 Correct 342 ms 13092 KB Output is correct
4 Correct 344 ms 13032 KB Output is correct
5 Correct 348 ms 13032 KB Output is correct
6 Correct 348 ms 13148 KB Output is correct
7 Correct 342 ms 13048 KB Output is correct
8 Correct 346 ms 13032 KB Output is correct
9 Correct 355 ms 13028 KB Output is correct
10 Correct 346 ms 13024 KB Output is correct
11 Correct 343 ms 13284 KB Output is correct
12 Correct 340 ms 13028 KB Output is correct
13 Correct 345 ms 13040 KB Output is correct
14 Correct 342 ms 13036 KB Output is correct
15 Correct 338 ms 13144 KB Output is correct
16 Correct 346 ms 13032 KB Output is correct
17 Correct 358 ms 13032 KB Output is correct
18 Correct 350 ms 13132 KB Output is correct
19 Correct 343 ms 13060 KB Output is correct
20 Correct 352 ms 13084 KB Output is correct
21 Correct 345 ms 13136 KB Output is correct
22 Correct 351 ms 11680 KB Output is correct
23 Correct 332 ms 11652 KB Output is correct
24 Correct 341 ms 11644 KB Output is correct
25 Correct 337 ms 11620 KB Output is correct
26 Correct 341 ms 11632 KB Output is correct
27 Correct 340 ms 11744 KB Output is correct
28 Correct 347 ms 11656 KB Output is correct
29 Correct 341 ms 11760 KB Output is correct
30 Correct 339 ms 11608 KB Output is correct
31 Correct 350 ms 11796 KB Output is correct
32 Correct 341 ms 11640 KB Output is correct
33 Correct 351 ms 11696 KB Output is correct
34 Correct 344 ms 11596 KB Output is correct
35 Correct 341 ms 11724 KB Output is correct
36 Correct 338 ms 11628 KB Output is correct
37 Correct 342 ms 11684 KB Output is correct
38 Correct 339 ms 11664 KB Output is correct
39 Correct 338 ms 11652 KB Output is correct
40 Correct 347 ms 11624 KB Output is correct
41 Correct 343 ms 11596 KB Output is correct
42 Correct 343 ms 11716 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 12192 KB Output is correct
2 Correct 342 ms 13164 KB Output is correct
3 Correct 342 ms 13092 KB Output is correct
4 Correct 344 ms 13032 KB Output is correct
5 Correct 348 ms 13032 KB Output is correct
6 Correct 348 ms 13148 KB Output is correct
7 Correct 342 ms 13048 KB Output is correct
8 Correct 346 ms 13032 KB Output is correct
9 Correct 355 ms 13028 KB Output is correct
10 Correct 346 ms 13024 KB Output is correct
11 Correct 343 ms 13284 KB Output is correct
12 Correct 340 ms 13028 KB Output is correct
13 Correct 345 ms 13040 KB Output is correct
14 Correct 342 ms 13036 KB Output is correct
15 Correct 338 ms 13144 KB Output is correct
16 Correct 346 ms 13032 KB Output is correct
17 Correct 358 ms 13032 KB Output is correct
18 Correct 350 ms 13132 KB Output is correct
19 Correct 343 ms 13060 KB Output is correct
20 Correct 352 ms 13084 KB Output is correct
21 Correct 345 ms 13136 KB Output is correct
22 Correct 351 ms 11680 KB Output is correct
23 Correct 332 ms 11652 KB Output is correct
24 Correct 341 ms 11644 KB Output is correct
25 Correct 337 ms 11620 KB Output is correct
26 Correct 341 ms 11632 KB Output is correct
27 Correct 340 ms 11744 KB Output is correct
28 Correct 347 ms 11656 KB Output is correct
29 Correct 341 ms 11760 KB Output is correct
30 Correct 339 ms 11608 KB Output is correct
31 Correct 350 ms 11796 KB Output is correct
32 Correct 341 ms 11640 KB Output is correct
33 Correct 351 ms 11696 KB Output is correct
34 Correct 344 ms 11596 KB Output is correct
35 Correct 341 ms 11724 KB Output is correct
36 Correct 338 ms 11628 KB Output is correct
37 Correct 342 ms 11684 KB Output is correct
38 Correct 339 ms 11664 KB Output is correct
39 Correct 338 ms 11652 KB Output is correct
40 Correct 347 ms 11624 KB Output is correct
41 Correct 343 ms 11596 KB Output is correct
42 Correct 343 ms 11716 KB Output is correct
43 Incorrect 349 ms 11524 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 12192 KB Output is correct
2 Correct 342 ms 13164 KB Output is correct
3 Correct 342 ms 13092 KB Output is correct
4 Correct 344 ms 13032 KB Output is correct
5 Correct 348 ms 13032 KB Output is correct
6 Correct 348 ms 13148 KB Output is correct
7 Correct 342 ms 13048 KB Output is correct
8 Correct 346 ms 13032 KB Output is correct
9 Correct 355 ms 13028 KB Output is correct
10 Correct 346 ms 13024 KB Output is correct
11 Correct 343 ms 13284 KB Output is correct
12 Correct 340 ms 13028 KB Output is correct
13 Correct 345 ms 13040 KB Output is correct
14 Correct 342 ms 13036 KB Output is correct
15 Correct 338 ms 13144 KB Output is correct
16 Correct 346 ms 13032 KB Output is correct
17 Correct 358 ms 13032 KB Output is correct
18 Correct 350 ms 13132 KB Output is correct
19 Correct 343 ms 13060 KB Output is correct
20 Correct 352 ms 13084 KB Output is correct
21 Correct 345 ms 13136 KB Output is correct
22 Correct 351 ms 11680 KB Output is correct
23 Correct 332 ms 11652 KB Output is correct
24 Correct 341 ms 11644 KB Output is correct
25 Correct 337 ms 11620 KB Output is correct
26 Correct 341 ms 11632 KB Output is correct
27 Correct 340 ms 11744 KB Output is correct
28 Correct 347 ms 11656 KB Output is correct
29 Correct 341 ms 11760 KB Output is correct
30 Correct 339 ms 11608 KB Output is correct
31 Correct 350 ms 11796 KB Output is correct
32 Correct 341 ms 11640 KB Output is correct
33 Correct 351 ms 11696 KB Output is correct
34 Correct 344 ms 11596 KB Output is correct
35 Correct 341 ms 11724 KB Output is correct
36 Correct 338 ms 11628 KB Output is correct
37 Correct 342 ms 11684 KB Output is correct
38 Correct 339 ms 11664 KB Output is correct
39 Correct 338 ms 11652 KB Output is correct
40 Correct 347 ms 11624 KB Output is correct
41 Correct 343 ms 11596 KB Output is correct
42 Correct 343 ms 11716 KB Output is correct
43 Incorrect 349 ms 11524 KB Output isn't correct
44 Halted 0 ms 0 KB -