Submission #198427

#	Time	Username	Problem	Language	Result	Execution time	Memory
198427		model_code	Squirrel (RMI18_squirrel)	C11	50 / 100	4798 ms	1144 KiB

squirrel

/**
 * Author: Catalin Francu
 *
 * Method: for every 2 <= X < MAX_COORD, store a list of distinct prime factors of X.
 * To compute coprime(X, Y), merge the two lists and look for a common factor.
 **/
#include <stdio.h>

#define MAX_FACTORS 6
#define MAX_COORD 50000
#define SENTRY MAX_COORD

unsigned short f[MAX_COORD][MAX_FACTORS + 1]; /* 6 factors + sentry */
unsigned short numf[MAX_COORD];

/* variables for fractal walking */
int delta[8][2] =
  { { -1, 0 }, { -1, -1, }, { 0, -1 }, { 1, -1 },
    { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 } };
int result; /* global -- is this faster? */

void sieve() {
  int d, i;

  for (d = 2; d < MAX_COORD; d++) {
    if (!numf[d]) { /* d is a prime */
      for (i = d; i < MAX_COORD; i += d) { /* every d-th number has d as a factor */
        f[i][numf[i]++] = d;
      }
    }
  }

  for (i = 0; i < MAX_COORD; i++) {
    f[i][numf[i]] = SENTRY;
  }
}

int coprime(int a, int b) {
  if (a == 0) {
    return (b == 1);
  }
  if (b == 0) {
    return (a == 1);
  }

  /* merge factor lists */
  int i = 0, j = 0;
  while (f[a][i] != f[b][j]) {
    if (f[a][i] < f[b][j]) {
      i++;
    } else {
      j++;
    }
  }

  return f[a][i] == SENTRY;
}

void fractal(int x, int y, int len, int dir) {

  int nextLen = (dir & 1) ? len : (len >> 1);

  /* skip the starting point, but include the endpoint */
  while (len--) {
    x += delta[dir][0];
    y += delta[dir][1];
    result += coprime(x, y);
  }

  if (nextLen) {
    fractal(x, y, nextLen, (dir + 1) & 7);
    fractal(x, y, nextLen, (dir - 1) & 7);
  }
}

int main() {
  sieve();

  int m, n, numFractals, x0, y0, len;

  scanf("%d %d %d ", &m, &n, &numFractals);

  while (numFractals--) {
    scanf("%d %d %d", &x0, &y0, &len);
    x0--; y0--; /* x0 and y0 should be relative to the observer at (1, 1) */

    /* the starting point is not included in the recursion */
    result += coprime(x0, y0);
    fractal(x0, y0, len, 0);
  }

  printf("%d\n", result);

  return 0;
}

Compilation message (stderr)

squirrel.c: In function 'main':
squirrel.c:81:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d ", &m, &n, &numFractals);
   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
squirrel.c:84:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &x0, &y0, &len);
     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 50