Submission #922616

#	Time	Username	Problem	Language	Result	Execution time	Memory
922616		rainboy	April Fools (LMIO17_faktai)	C11	100 / 100	42 ms	9648 KiB

faktai

#include <stdio.h>

#define N	20

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int cnt[1 << N];

void init() {
	int b;

	for (b = 1; b < 1 << N; b++)
		cnt[b] = cnt[b & b - 1] + 1;
}

int main() {
	static int ss[1 << N];
	static char bad[1 << N];
	int n, m, h, i, b, mn, mx;

	init();
	scanf("%d%d", &m, &n);
	for (h = 0; h < m; h++) {
		int k;

		scanf("%d", &k);
		b = 0;
		while (k--) {
			scanf("%d", &i), i--;
			b ^= 1 << i;
			ss[1 << i]++;
		}
		bad[(1 << n) - 1 ^ b] = 1;
	}
	for (b = 0; b < 1 << n; b++)
		ss[b] = ss[b & b - 1] + ss[b & -b];
	for (i = 0; i < n; i++)
		for (b = 0; b < 1 << n; b++)
			if ((b & 1 << i) == 0 && bad[b | 1 << i])
				bad[b] = 1;
	mn = n + 1, mx = -1;
	for (b = 0; b < 1 << n; b++)
		if (!bad[b] && ss[b] == m)
			mn = min(mn, cnt[b]), mx = max(mx, cnt[b]);
	printf("%d %d\n", mn, mx);
	return 0;
}

Compilation message (stderr)

faktai.c: In function 'init':
faktai.c:14:22: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |   cnt[b] = cnt[b & b - 1] + 1;
      |                    ~~^~~
faktai.c: In function 'main':
faktai.c:34:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   34 |   bad[(1 << n) - 1 ^ b] = 1;
      |       ~~~~~~~~~^~~
faktai.c:37:20: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   37 |   ss[b] = ss[b & b - 1] + ss[b & -b];
      |                  ~~^~~
faktai.c:23:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d%d", &m, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~
faktai.c:27:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%d", &k);
      |   ^~~~~~~~~~~~~~~
faktai.c:30:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60