oj.uz

Submission #463821

# Submission time Handle Problem Language Result Execution time Memory
463821 2021-08-11T20:26:18 Z rainboy Sirni (COCI17_sirni) C
140 / 140
 1702 ms 283504 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 120868 KB Output is correct
2 Correct 165 ms 122444 KB Output is correct
3 Correct 121 ms 121272 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 117752 KB Output is correct
2 Correct 205 ms 118288 KB Output is correct
3 Correct 119 ms 121100 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 121112 KB Output is correct
2 Correct 117 ms 118836 KB Output is correct
3 Correct 119 ms 121152 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 130464 KB Output is correct
2 Correct 328 ms 141960 KB Output is correct
3 Correct 294 ms 138024 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 120772 KB Output is correct
2 Correct 353 ms 136632 KB Output is correct
3 Correct 276 ms 129856 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 139064 KB Output is correct
2 Correct 291 ms 138448 KB Output is correct
3 Correct 230 ms 130840 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 121448 KB Output is correct
2 Correct 320 ms 137468 KB Output is correct
3 Correct 274 ms 135064 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 145596 KB Output is correct
2 Correct 957 ms 226364 KB Output is correct
3 Correct 323 ms 150584 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 144268 KB Output is correct
2 Correct 1151 ms 238156 KB Output is correct
3 Correct 383 ms 157300 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 130276 KB Output is correct
2 Correct 1702 ms 283504 KB Output is correct
3 Correct 294 ms 137396 KB Output is correct