oj.uz

Submission #463819

# Submission time Handle Problem Language Result Execution time Memory
463819 2021-08-11T20:17:40 Z rainboy Sirni (COCI17_sirni) C
28 / 140
 363 ms 145356 KB 
#include <stdio.h>
#include <string.h>

#define N	100000
#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) {
				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 109 ms 120804 KB Output is correct
2 Correct 161 ms 122452 KB Output is correct
3 Correct 113 ms 121116 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 161 ms 117764 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 110 ms 121136 KB Output is correct
2 Correct 109 ms 118752 KB Output is correct
3 Correct 113 ms 121128 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 120788 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 138184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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