oj.uz

Submission #882155

# Submission time Handle Problem Language Result Execution time Memory
882155 2023-12-02T17:29:22 Z rainboy Norela (info1cup18_norela) C
100 / 100
 2 ms 472 KB 
#include <stdio.h>

#define N	24
#define M	(1 << N / 2)

unsigned int X = 12345;

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

int kk[M];

void init() {
	int b;

	for (b = 1; b < M; b++)
		kk[b] = kk[b & b - 1] + 1;
}

long long *xx;

int compare(int b1, int b2) {
	return xx[b1] != xx[b2] ? (xx[b1] < xx[b2] ? -1 : 1) : (kk[b1] != kk[b2] ? kk[b1] - kk[b2] : b2 - b1);
}

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

		while (j < k) {
			int c = compare(bb[j], b);

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

int main() {
	static long long aa[N], xx1[M], xx2[M];
	static int bb1[M], bb2[M];
	int n, n1, n2, m1, m2, l, k, h1, h2, i, j, b1, b1_, b2, b2_;

	init();
	scanf("%d%d", &l, &n), n1 = n / 2, n2 = n - n1;
	for (i = n - 1; i >= 0; i--) {
		scanf("%d", &k);
		while (k--) {
			scanf("%d", &j), j--;
			aa[i] |= 1LL << j;
		}
	}
	m1 = 1 << n1;
	for (b1 = 0; b1 < m1; b1++) {
		xx1[b1] = 0;
		for (i = 0; i < n1; i++)
			if ((b1 & 1 << i) != 0)
				xx1[b1] ^= aa[i];
	}
	for (b1 = 0; b1 < m1; b1++)
		bb1[b1] = b1;
	xx = xx1, sort(bb1, 0, m1);
	m2 = 1 << n2;
	for (b2 = 0; b2 < m2; b2++) {
		xx2[b2] = (1LL << l) - 1;
		for (i = 0; i < n2; i++)
			if ((b2 & 1 << i) != 0)
				xx2[b2] ^= aa[n1 + i];
	}
	for (b2 = 0; b2 < m2; b2++)
		bb2[b2] = b2;
	xx = xx2, sort(bb2, 0, m2);
	b1_ = -1, b2_ = -1;
	for (h1 = 0, h2 = 0; h1 < m1; h1++) {
		while (h2 < m2 && xx2[bb2[h2]] < xx1[bb1[h1]])
			h2++;
		if (h2 < m2 && xx2[bb2[h2]] == xx1[bb1[h1]]) {
			b1 = bb1[h1], b2 = bb2[h2];
			if (b1_ == -1 && b2_ == -1 || (kk[b1_] + kk[b2_] > kk[b1] + kk[b2] || kk[b1_] + kk[b2_] == kk[b1] + kk[b2] && (b2_ < b2 || b2_ == b2 && b1_ < b1)))
				b1_ = b1, b2_ = b2;
		}
	}
	printf("%d\n", kk[b1_] + kk[b2_]);
	for (i = n2 - 1; i >= 0; i--)
		if ((b2_ & 1 << i) != 0)
			printf("%d ", n - (n1 + i));
	for (i = n1 - 1; i >= 0; i--)
		if ((b1_ & 1 << i) != 0)
			printf("%d ", n - i);
	printf("\n");
	return 0;
}

Compilation message

norela.c: In function 'init':
norela.c:18:20: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |   kk[b] = kk[b & b - 1] + 1;
      |                  ~~^~~
norela.c: In function 'main':
norela.c:89:137: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   89 |    if (b1_ == -1 && b2_ == -1 || (kk[b1_] + kk[b2_] > kk[b1] + kk[b2] || kk[b1_] + kk[b2_] == kk[b1] + kk[b2] && (b2_ < b2 || b2_ == b2 && b1_ < b1)))
      |                                                                                                                               ~~~~~~~~~~^~~~~~~~~~~
norela.c:89:111: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   89 |    if (b1_ == -1 && b2_ == -1 || (kk[b1_] + kk[b2_] > kk[b1] + kk[b2] || kk[b1_] + kk[b2_] == kk[b1] + kk[b2] && (b2_ < b2 || b2_ == b2 && b1_ < b1)))
      |                                                                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
norela.c:89:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   89 |    if (b1_ == -1 && b2_ == -1 || (kk[b1_] + kk[b2_] > kk[b1] + kk[b2] || kk[b1_] + kk[b2_] == kk[b1] + kk[b2] && (b2_ < b2 || b2_ == b2 && b1_ < b1)))
      |        ~~~~~~~~~~^~~~~~~~~~~~
norela.c:55:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d%d", &l, &n), n1 = n / 2, n2 = n - n1;
      |  ^~~~~~~~~~~~~~~~~~~~~
norela.c:57:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d", &k);
      |   ^~~~~~~~~~~~~~~
norela.c:59:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |    scanf("%d", &j), j--;
      |    ^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 440 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 472 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 440 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 472 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 2 ms 348 KB Output is correct