oj.uz

Submission #479369

# Submission time Handle Problem Language Result Execution time Memory
479369 2021-10-11T13:49:33 Z rainboy Parametriziran (COCI19_parametriziran) C
110 / 110
 249 ms 1448 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1100 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 716 KB Output is correct
2 Correct 5 ms 716 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 896 KB Output is correct
2 Correct 10 ms 1100 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 716 KB Output is correct
2 Correct 9 ms 776 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 972 KB Output is correct
2 Correct 12 ms 588 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1100 KB Output is correct
2 Correct 18 ms 1052 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 1008 KB Output is correct
2 Correct 22 ms 844 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1188 KB Output is correct
2 Correct 65 ms 1204 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 1100 KB Output is correct
2 Correct 39 ms 972 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 1448 KB Output is correct
2 Correct 140 ms 1356 KB Output is correct