// 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
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
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
632 KB |
Output is correct |
| 2 |
Correct |
23 ms |
632 KB |
Output is correct |
| 3 |
Correct |
316 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
550 ms |
764 KB |
Output is correct |
| 2 |
Correct |
498 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
828 ms |
632 KB |
Output is correct |
| 2 |
Correct |
860 ms |
732 KB |
Output is correct |
| 3 |
Correct |
938 ms |
764 KB |
Output is correct |
| 4 |
Correct |
906 ms |
760 KB |
Output is correct |
| 5 |
Correct |
979 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1715 ms |
760 KB |
Output is correct |
| 2 |
Correct |
1779 ms |
760 KB |
Output is correct |
| 3 |
Correct |
1917 ms |
864 KB |
Output is correct |
| 4 |
Correct |
2015 ms |
760 KB |
Output is correct |
| 5 |
Correct |
2085 ms |
736 KB |
Output is correct |
| 6 |
Correct |
2172 ms |
760 KB |
Output is correct |
| 7 |
Correct |
2265 ms |
732 KB |
Output is correct |
| 8 |
Correct |
2281 ms |
760 KB |
Output is correct |
| 9 |
Correct |
2291 ms |
732 KB |
Output is correct |
| 10 |
Correct |
2276 ms |
632 KB |
Output is correct |
