Submission #738910

#	Time	Username	Problem	Language	Result	Execution time	Memory
738910		rainboy	Squirrel (RMI18_squirrel)	C11	100 / 100	3625 ms	996 KiB

squirrel

#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 (stderr)

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 / 15
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 50 / 50