Submission #554806

#	Time	Username	Problem	Language	Result	Execution time	Memory
554806		mircea_007	Squirrel (RMI18_squirrel)	C++17	55 / 100	2457 ms	972 KiB

squirrel

// This program was written on 7.04.2022
// for problem squirrel
// by Mircea Rebengiuc

#include <stdio.h>
#include <ctype.h>

#define MAXN 50000

typedef unsigned long long ull;

struct Vector { int x, y; };
static inline Vector operator + ( struct Vector a, struct Vector b ){ return { a.x + b.x, a.y + b.y }; }
static inline void operator += ( struct Vector &a, struct Vector b ){ a.x += b.x; a.y += b.y; }
static inline bool operator == ( struct Vector a, struct Vector b ){ return a.x == b.x && a.y == b.y; };

// sens anti-trigonometric
Vector d[4] = {
  {  0, -1 },
  {  1,  0 },
  {  0,  1 },
  { -1,  0 },
};

ull pmask[MAXN];
int left[MAXN];

bool coprime( Vector pair ){
  if( pair == (struct Vector){ 0, 1 } )
    return true;

  if( pair == (struct Vector){ 1, 0 } )
    return true;
  
  if( !pair.x || !pair.y )
    return false;

  if( pmask[pair.x] & pmask[pair.y] )
    return false;
  
  if( left[pair.x] == 1 )
    return true;

  return left[pair.x] != left[pair.y];
}

int fractal_without_root( Vector p, int r, int dir ){
  int retval = 0, i;
  Vector dl = d[dir] + d[(dir + 3) & 3], dr = d[dir] + d[(dir + 1) & 3];
  Vector pl, pr;

  if( r == 1 )
    return coprime( p + d[dir] );
  
  for( i = 0 ; i < r ; i++ ){
    p += d[dir];
    retval += coprime( p );
  }
  
  r >>= 1;
  
  pl = pr = p;
  
  for( i = 0 ; i < r ; i++ ){
    pl += dl;
    pr += dr;
    
    retval += coprime( pl ) + coprime( pr );
  }
  
  retval += fractal_without_root( pl, r, (dir + 3) & 3 );
  retval += fractal_without_root( pl, r, dir );
  retval += fractal_without_root( pr, r, dir );
  retval += fractal_without_root( pr, r, (dir + 1) & 3 );
  
  return retval;
}

int main(){
  FILE *fin, *fout;
  #ifdef LOCAL
  fin  = fopen( "squirrel.in",  "r" );
  fout = fopen( "squirrel.out", "w" );
  #else
  fin = stdin;
  fout = stdout;
  #endif
  
  int n, m, r, q, nv, total, max, d, i;
  Vector start;
  ull p2;
  
  fscanf( fin, "%d%d", &n, &m );
  max = n > m ? n : m;

  for( i = 2 ; i <= max ; i++ ){
    pmask[i] = 0ULL;
    left[i] = i;
  }

  p2 = 1ULL;
  for( d = 2 ; d * d <= max ; d++ ){
    if( !pmask[d] ){
      for( i = d ; i <= max ; i += d ){
        pmask[i] |= p2;
        while( !(left[i] % d) )
          left[i] /= d;
      }
      
      p2 <<= 1;
    }
  }
  
  total = 0;
  for( fscanf( fin, "%d", &q ) ; q-- ; ){
    fscanf( fin, "%d%d%d", &start.y, &start.x, &r );
    start += { -1, -1 };

    nv = coprime( start ) + fractal_without_root( start, r, 0 );

    //printf( "+%d\n", nv );
    total += nv;
  }
  
  fprintf( fout, "%d\n", total );
  
  #ifdef LOCAL
  fclose( fin );
  fclose( fout );
  #endif
  return 0;
}

Compilation message (stderr)

squirrel.cpp: In function 'int main()':
squirrel.cpp:93:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   fscanf( fin, "%d%d", &n, &m );
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
squirrel.cpp:115:14: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   for( fscanf( fin, "%d", &q ) ; q-- ; ){
      |        ~~~~~~^~~~~~~~~~~~~~~~~
squirrel.cpp:116:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     fscanf( fin, "%d%d%d", &start.y, &start.x, &r );
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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