oj.uz

답안 #198427

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198427 2020-01-26T02:41:30 Z model_code Squirrel (RMI18_squirrel) C
50 / 100
 4700 ms 1144 KB 
/**
 * 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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 1016 KB Output is correct
2 Correct 61 ms 1128 KB Output is correct
3 Correct 1135 ms 1144 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1850 ms 1016 KB Output is correct
2 Correct 1842 ms 1120 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3063 ms 1144 KB Output is correct
2 Correct 3154 ms 1120 KB Output is correct
3 Correct 3360 ms 1124 KB Output is correct
4 Correct 3453 ms 1124 KB Output is correct
5 Correct 3576 ms 1144 KB Output is correct

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4781 ms 1144 KB Time limit exceeded
2 Execution timed out 4795 ms 1016 KB Time limit exceeded
3 Execution timed out 4787 ms 1016 KB Time limit exceeded
4 Execution timed out 4748 ms 1016 KB Time limit exceeded
5 Execution timed out 4776 ms 1016 KB Time limit exceeded
6 Execution timed out 4787 ms 1016 KB Time limit exceeded
7 Execution timed out 4798 ms 1016 KB Time limit exceeded
8 Execution timed out 4793 ms 1016 KB Time limit exceeded
9 Execution timed out 4793 ms 1016 KB Time limit exceeded
10 Execution timed out 4782 ms 1016 KB Time limit exceeded