Submission #545927

#	Time	Username	Problem	Language	Result	Execution time	Memory
545927		rainboy	Cubeword (CEOI19_cubeword)	C11	100 / 100	255 ms	10928 KiB

cubeword

#include <ctype.h>
#include <stdio.h>
#include <string.h>

#define N	100000
#define A	62
#define L	8
#define MD	998244353

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

char *ss[N * 2];

void sort(char **ss, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r;
		char *s = ss[l + rand_() % (r - l)], *tmp;

		while (j < k) {
			int c = strcmp(ss[j], s);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ss[i], ss[i] = ss[j], ss[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ss[j], ss[j] = ss[k], ss[k] = tmp;
			}
		}
		sort(ss, l, i);
		l = k;
	}
}

int idx(char c) {
	return isdigit(c) ? c - '0' : (isupper(c) ? c - 'A' + 10 : c - 'a' + 36);
}

int count(int a, int b, int c, int d) {
	if (a == b && b == c && c == d)
		return 1;
	else if (a == b && b == c || b == c && c == d || c == d && d == a || d == a && a == b)
		return 4;
	else if (a == b && c == d || a == c && b == d || a == d && b == c)
		return 6;
	else if (a == b || a == c || a == d || b == c || b == d || c == d)
		return 12;
	else
		return 24;
}

int main() {
	static int kk[L][A][A];
	static long long kk_[A][A][A];
	int n, i, l, a, b, c, d;
	long long ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		static char s[16], t[16];
		int h;

		scanf("%s", s), l = strlen(s);
		for (h = 0; h < l; h++)
			t[h] = s[l - 1 - h];
		t[l] = 0;
		ss[i << 1 | 0] = strdup(s), ss[i << 1 | 1] = strdup(t);
	}
	sort(ss, 0, n * 2);
	for (i = 0; i < n * 2; i++)
		if (i == 0 || strcmp(ss[i - 1], ss[i]) != 0) {
			l = strlen(ss[i]);
			kk[l - 3][idx(ss[i][0])][idx(ss[i][l - 1])]++;
		}
	ans = 0;
	for (l = 0; l < L; l++) {
		for (a = 0; a < A; a++)
			for (b = a; b < A; b++)
				for (c = b; c < A; c++) {
					long long k;

					k = 0;
					for (d = 0; d < A; d++)
						k += (long long) kk[l][a][d] * kk[l][b][d] * kk[l][c][d];
					kk_[a][b][c] = kk_[a][c][b] = kk_[b][a][c] = kk_[b][c][a] = kk_[c][a][b] = kk_[c][b][a] = k % MD;
				}
		for (a = 0; a < A; a++)
			for (b = a; b < A; b++)
				for (c = b; c < A; c++)
					for (d = c; d < A; d++)
						ans += (long long) kk_[a][b][c] * kk_[b][c][d] % MD * kk_[c][d][a] % MD * kk_[d][a][b] % MD * count(a, b, c, d);
		ans %= MD;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

cubeword.c: In function 'count':
cubeword.c:48:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |  else if (a == b && b == c || b == c && c == d || c == d && d == a || d == a && a == b)
      |           ~~~~~~~^~~~~~~~~
cubeword.c:48:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |  else if (a == b && b == c || b == c && c == d || c == d && d == a || d == a && a == b)
      |                                                   ~~~~~~~^~~~~~~~~
cubeword.c:48:78: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |  else if (a == b && b == c || b == c && c == d || c == d && d == a || d == a && a == b)
      |                                                                       ~~~~~~~^~~~~~~~~
cubeword.c:50:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   50 |  else if (a == b && c == d || a == c && b == d || a == d && b == c)
      |           ~~~~~~~^~~~~~~~~
cubeword.c:50:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   50 |  else if (a == b && c == d || a == c && b == d || a == d && b == c)
      |                                                   ~~~~~~~^~~~~~~~~
cubeword.c: In function 'main':
cubeword.c:64:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
cubeword.c:69:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%s", s), l = strlen(s);
      |   ^~~~~~~~~~~~~~

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