oj.uz

Submission #463820

# Submission time Handle Problem Language Result Execution time Memory
463820 2021-08-11T20:19:43 Z rainboy Sirni (COCI17_sirni) C
28 / 140
 363 ms 145372 KB 
#include <assert.h>
#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])
			continue;
		for (b = a; b <= A; b += a) {
			int c = next[b == a ? a + 1 : b];

			if (c == b)
				used[c] = 0;
			if (c <= A && c < b + a) {
				assert(m < M);
				aa[m] = a, bb[m] = c, ww[m] = c - 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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 121028 KB Output is correct
2 Correct 165 ms 122444 KB Output is correct
3 Correct 115 ms 121156 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 160 ms 117812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 121092 KB Output is correct
2 Correct 125 ms 118840 KB Output is correct
3 Correct 115 ms 121088 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 129804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 120656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 363 ms 138348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 232 ms 121028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 145372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 275 ms 144044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 130296 KB Output isn't correct
2 Halted 0 ms 0 KB -