Submission #198428

#	Time	Username	Problem	Language	Result	Execution time	Memory
198428		model_code	Squirrel (RMI18_squirrel)	C11	100 / 100	2291 ms	864 KiB

squirrel

// by Cristian Francu on 2018-09-25
// source O(jumps) + O(sqrt(max coord))
// uses no divisions, but a fast coprime test using bit masks
#include <stdio.h>

#define MAX_COORD 50000 /* can be maximum 51528 */
#define SQRT_MAX_COORD 223

char prim[SQRT_MAX_COORD + 1];
struct { unsigned masklo; unsigned short maskhi, rest; } fact[MAX_COORD+1];
// directions, starting with east (trigonometric)
int ldir[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int cdir[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };

inline int coprime( int a, int b ) {
  // compensating in main code for (0, 1) and (1, 0)
  if (a == 0) {
    return (b == 1);
  }
  if (b == 0) {
    return (a == 1);
  }
  /* works a little slower
  if ( (a && b) == 0 )   // is one of the values zero?
    return (a + b == 1); // one is zero one is one - visible
  */
  /* compensating in main code for (1, 1)
  if ( a == 1 && b == 1 ) // (1, 1) is visible
    return 1;
  */
  return (fact[a].masklo & fact[b].masklo) == 0 &&
    (fact[a].maskhi & fact[b].maskhi) == 0 &&
    fact[a].rest != fact[b].rest;
}

int traversal( int l, int c, int len, int dir ) {
  int i, s;

  s = 0;
  for ( i = 1; i <= len; i++ )
    s += coprime( l + i * ldir[dir], c + i * cdir[dir] );

  if ( len > 1 ) {
    l += len * ldir[dir];
    c += len * cdir[dir];
    len >>= 1;

    for ( i = 1; i <= len; i++ )
      s += coprime( l + i * ldir[(dir+1) & 7], c + i * cdir[(dir+1) & 7] );

    s += traversal( l + len * ldir[(dir+1) & 7], c + len * cdir[(dir+1) & 7],
                    len, (dir+2) & 7 );
    s += traversal( l + len * ldir[(dir+1) & 7], c + len * cdir[(dir+1) & 7],
                    len, dir );

    for ( i = 1; i <= len; i++ )
      s += coprime( l + i * ldir[(dir+7) & 7], c + i * cdir[(dir+7) & 7] );
    
    s += traversal( l + len * ldir[(dir+7) & 7], c + len * cdir[(dir+7) & 7],
                    len, dir );
    s += traversal( l + len * ldir[(dir+7) & 7], c + len * cdir[(dir+7) & 7],
                    len, (dir+6) & 7 );
  }
  return s;
}

int main() {
  int m, n, f, l, c, sum, i, llen, p, d, dir;
  unsigned long long mask;

  // Erathostenes sieve up to SQRT_MAX_COORD
  for ( p = 2; p * p <= SQRT_MAX_COORD; p++ )
    if ( prim[p] == 0 )
      for ( d = p * p; d <= SQRT_MAX_COORD; d += p )
        prim[d] = 1;

  // we build primes mask of zero - zero is divisible by all numbers
  fact[0].maskhi = (unsigned short)-1;
  fact[0].masklo = (unsigned)-1;

  // we build primes masks of all numbers from 2 to MAX_COORD
  // first set the rest to the number itself (including the non-prime 1)
  for ( p = 1; p <= MAX_COORD; p++ )
    fact[p].rest = (unsigned short)p;

  // then compute prime masks and the rests (remainders)
  mask = 1;
  for ( p = 2; p <= SQRT_MAX_COORD; p++ )
    if ( prim[p] == 0 ) {
      for ( d = p; d <= MAX_COORD; d += p ) {
        fact[d].masklo |= (unsigned)mask; // I think this should be fine
        fact[d].maskhi |= mask >> 32;
        do
          fact[d].rest /= p;
        while ( fact[d].rest % p == 0 );
      }
      mask <<= 1;
    }

  // we want the numbers that don't have a remainder (rest) to be different
  // from any other number's remainder, since it does not participate in
  // the comparison, so we reset the rest back to the number itself
  for ( p = 2; p <= MAX_COORD; p++ )
    if ( fact[p].rest == 1 )
      fact[p].rest = (unsigned short)p;
  
  scanf( "%d%d%d", &m, &n, &f ); // lines, columns, no. fractals
  sum = 0;
  for ( i = 0; i < f; i++ ) { // read f fractals
    scanf( "%d%d%d", &l, &c, &llen ); // start line, start column, length of first branch
    l--; // adjust for coordinates starting with (0, 0), not (1, 1)
    c--;

    if ( llen == 1 && l <= 2 && c == 1 ) // adjusting for (1, 1)
      sum++;
    else if ( llen == 2 && ( (l == 4 && (c == 2 || c == 3)) ||
                            (l == 5 && c == 2) ) )
      sum++; // adjusting for (1, 1)

    sum += coprime( l, c ); // add visibility of starting point
    dir = 2;  // first direction is north
    
    sum += traversal( l, c, llen, dir );
  }

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

  return 0;
}

Compilation message (stderr)

squirrel.c: In function 'main':
squirrel.c:107:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf( "%d%d%d", &m, &n, &f ); // lines, columns, no. fractals
   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
squirrel.c:110:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
     scanf( "%d%d%d", &l, &c, &llen ); // start line, start column, length of first branch
     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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