Submission #463821

#	Time	Username	Problem	Language	Result	Execution time	Memory
463821		rainboy	Sirni (COCI17_sirni)	C11	140 / 140	1702 ms	283504 KiB

sirni

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

#define A	10000000
#define M	50000000
#define INF	0x3f3f3f3f

int ds[A + 1];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

int join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}


int main() {
	static char used[A + 1];
	static int next[A + 1], kk[A + 1], aa[M], bb[M], ww[M], hh[M];
	int n, m, h, h_, a, b, ans;

	scanf("%d", &n);
	while (n--) {
		scanf("%d", &a);
		used[a] = 1;
	}
	for (a = A; a >= 0; a--)
		next[a] = used[a] ? a : (a == A ? INF : next[a + 1]);
	m = 0;
	for (a = 1; a < A; a++)
		if (used[a]) {
			b = next[a + 1];
			if (b <= A && b < a * 2) {
				aa[m] = a, bb[m] = b, ww[m] = b - a, m++;
				kk[ww[m - 1] + 1]++;
			}
		}
	for (a = 1; a < A; a++)
		if (used[a])
			for (b = a + a; b <= A; b += a) {
				if (next[b] == b)
					used[next[b]] = 0;
				if (next[b] <= A && next[b] < b + a) {
					aa[m] = a, bb[m] = next[b], ww[m] = next[b] - b, m++;
					kk[ww[m - 1] + 1]++;
				}
			}
	for (a = 1; a <= A; a++)
		kk[a] += kk[a - 1];
	for (h = 0; h < m; h++)
		hh[kk[ww[h]]++] = h;
	memset(ds, -1, (A + 1) * sizeof *ds);
	ans = 0;
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		if (join(aa[h_], bb[h_]))
			ans += ww[h_];
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

sirni.c: In function 'main':
sirni.c:35:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
sirni.c:37:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d", &a);
      |   ^~~~~~~~~~~~~~~

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