oj.uz

Submission #554820

# Submission time Handle Problem Language Result Execution time Memory
554820 2022-04-29T13:17:43 Z mircea_007 Squirrel (RMI18_squirrel) C++17
100 / 100
 2360 ms 972 KB 
// 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.x )
    return pair.y == 1;

  if( !pair.y )
    return pair.x == 1;

  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 = 1 ; 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;
    }
  }
  
  //printf( "(1, 1) ==> %d\n", coprime( { 1, 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 );

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

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 17 ms 340 KB Output is correct
3 Correct 312 ms 852 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 864 KB Output is correct
2 Correct 502 ms 852 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 856 KB Output is correct
2 Correct 841 ms 972 KB Output is correct
3 Correct 873 ms 852 KB Output is correct
4 Correct 914 ms 972 KB Output is correct
5 Correct 966 ms 856 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1674 ms 852 KB Output is correct
2 Correct 1799 ms 852 KB Output is correct
3 Correct 1861 ms 852 KB Output is correct
4 Correct 1953 ms 860 KB Output is correct
5 Correct 2202 ms 856 KB Output is correct
6 Correct 2360 ms 852 KB Output is correct
7 Correct 2327 ms 860 KB Output is correct
8 Correct 2281 ms 852 KB Output is correct
9 Correct 2300 ms 852 KB Output is correct
10 Correct 2237 ms 864 KB Output is correct