oj.uz

Submission #463817

# Submission time Handle Problem Language Result Execution time Memory
463817 2021-08-11T20:14:09 Z rainboy Sirni (COCI17_sirni) C
28 / 140
 393 ms 146096 KB 
#include <stdio.h>
#include <string.h>

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

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

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 < b + a) {
				aa[m] = a, bb[m] = c, ww[m] = c - b, m++;
				kk[ww[m - 1]]++;
			}
		}
	}
	for (a = 1; a <= A; a++)
		kk[a] += kk[a - 1];
	for (h = 0; h < m; h++)
		hh[kk[ww[h] - 1]++] = 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:38:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
sirni.c:40:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d", &a);
      |   ^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 120932 KB Output is correct
2 Correct 164 ms 122452 KB Output is correct
3 Correct 110 ms 121196 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 117824 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 118 ms 121164 KB Output is correct
2 Correct 112 ms 118852 KB Output is correct
3 Correct 112 ms 121108 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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