Submission #479369

#	Time	Username	Problem	Language	Result	Execution time	Memory
479369		rainboy	Parametriziran (COCI19_parametriziran)	C11	110 / 110	249 ms	1448 KiB

Main

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

#define N	50000
#define M	6
#define A	26

char cc[N][M + 1]; int m;

void sort(int *ii, int n, int j) {
	static int kk[A + 1], ii_[N];
	int i, i_, a;

	memset(kk, 0, (A + 1) * sizeof *kk);
	for (i = 0; i < n; i++) {
		a = cc[ii[i]][j] - 'a';
		kk[a + 1]++;
	}
	for (a = 1; a <= A; a++)
		kk[a] += kk[a - 1];
	for (i = 0; i < n; i++) {
		i_ = ii[i], a = cc[i_][j] - 'a';
		ii_[kk[a]++] = i_;
	}
	memcpy(ii, ii_, n * sizeof *ii_);
}

int compare(int i1, int i2, int b) {
	int j;

	for (j = 0; j < m; j++)
		if ((b & 1 << j) != 0 && cc[i1][j] != cc[i2][j])
			return cc[i1][j] - cc[i2][j];
	return 0;
}

int main() {
	static int ii[1 << M][N], kk[1 << M];
	int n, g, g_, h, h_, i, j, b1, b2, b, ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%s", cc[i]);
		b = 0;
		for (j = 0; j < m; j++)
			if (cc[i][j] != '?')
				b |= 1 << j;
		ii[b][kk[b]++] = i;
	}
	ans = 0;
	for (b1 = 0; b1 < 1 << m; b1++)
		for (b2 = b1; b2 < 1 << m; b2++) {
			b = b1 & b2;
			for (j = m - 1; j >= 0; j--)
				if ((b & 1 << j) != 0) {
					sort(ii[b1], kk[b1], j);
					if (b1 != b2)
						sort(ii[b2], kk[b2], j);
				}
			g = 0, h = 0;
			while (g < kk[b1] && h < kk[b2]) {
				int c = compare(ii[b1][g], ii[b2][h], b);

				if (c < 0)
					g++;
				else if (c > 0)
					h++;
				else {
					g_ = g + 1;
					while (g_ < kk[b1] && compare(ii[b1][g_], ii[b1][g], b) == 0)
						g_++;
					h_ = h + 1;
					while (h_ < kk[b2] && compare(ii[b2][h_], ii[b2][h], b) == 0)
						h_++;
					ans += b1 == b2 ? (g_ - g) * (g_ - g - 1) / 2 : (g_ - g) * (h_ - h);
					g = g_, h = h_;
				}
			}
		}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

parametriziran.c: In function 'main':
parametriziran.c:41:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
parametriziran.c:43:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11