oj.uz

Submission #738910

# Submission time Handle Problem Language Result Execution time Memory
738910 2023-05-09T15:47:36 Z rainboy Squirrel (RMI18_squirrel) C
100 / 100
 3625 ms 996 KB 
#include <stdio.h>

#define N	50000

int di[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dj[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

long long bb[N + 1]; int pp[N + 1];

void init() {
	int i, j, k;

	for (i = 1; i <= N; i++)
		bb[i] = 0, pp[i] = i;
	k = 0;
	for (i = 2; i * i <= N; i++) {
		if (pp[i] != i)
			continue;
		for (j = i; j <= N; j += i) {
			bb[j] |= 1LL << k;
			while (pp[j] % i == 0)
				pp[j] /= i;
		}
		k++;
	}
}

int visible(int i, int j) {
	if (i == 0)
		return j == 1;
	if (j == 0)
		return i == 1;
	return (bb[i] & bb[j]) == 0 && (pp[i] == 1 || pp[i] != pp[j]);
}

int cnt;

void count(int i, int j, int l, int d) {
	int k;

	for (k = 1; k <= l; k++)
		if (visible(i + di[d] * k, j + dj[d] * k))
			cnt++;
	if (l == 1)
		return;
	for (k = 1; k <= l / 2; k++) {
		if (visible(i + di[d] * l + di[(d + 7) % 8] * k, j + dj[d] * l + dj[(d + 7) % 8] * k))
			cnt++;
		if (visible(i + di[d] * l + di[(d + 1) % 8] * k, j + dj[d] * l + dj[(d + 1) % 8] * k))
			cnt++;
	}
	count(i + di[d] * l + di[(d + 7) % 8] * l / 2, j + dj[d] * l + dj[(d + 7) % 8] * l / 2, l / 2, d);
	count(i + di[d] * l + di[(d + 7) % 8] * l / 2, j + dj[d] * l + dj[(d + 7) % 8] * l / 2, l / 2, (d + 6) % 8);
	count(i + di[d] * l + di[(d + 1) % 8] * l / 2, j + dj[d] * l + dj[(d + 1) % 8] * l / 2, l / 2, d);
	count(i + di[d] * l + di[(d + 1) % 8] * l / 2, j + dj[d] * l + dj[(d + 1) % 8] * l / 2, l / 2, (d + 2) % 8);
}

int main() {
	int q;

	init();
	scanf("%*d%*d%d", &q);
	while (q--) {
		int i, j, l;

		scanf("%d%d%d", &i, &j, &l), i--, j--;
		if (visible(i, j))
			cnt++;
		count(i, j, l, 0);
	}
	printf("%d\n", cnt);
	return 0;
}

Compilation message

squirrel.c: In function 'main':
squirrel.c:62:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%*d%*d%d", &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
squirrel.c:66:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d%d%d", &i, &j, &l), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 852 KB Output is correct
2 Correct 25 ms 996 KB Output is correct
3 Correct 427 ms 856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 852 KB Output is correct
2 Correct 720 ms 856 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1231 ms 856 KB Output is correct
2 Correct 1218 ms 852 KB Output is correct
3 Correct 1245 ms 852 KB Output is correct
4 Correct 1336 ms 852 KB Output is correct
5 Correct 1344 ms 852 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2411 ms 864 KB Output is correct
2 Correct 2493 ms 852 KB Output is correct
3 Correct 2667 ms 852 KB Output is correct
4 Correct 2782 ms 864 KB Output is correct
5 Correct 3009 ms 856 KB Output is correct
6 Correct 3131 ms 852 KB Output is correct
7 Correct 3331 ms 860 KB Output is correct
8 Correct 3160 ms 856 KB Output is correct
9 Correct 3213 ms 856 KB Output is correct
10 Correct 3625 ms 860 KB Output is correct