oj.uz

Submission #554806

# Submission time Handle Problem Language Result Execution time Memory
554806 2022-04-29T12:58:25 Z mircea_007 Squirrel (RMI18_squirrel) C++17
55 / 100
 2457 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 == (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

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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Incorrect 18 ms 424 KB Output isn't correct
3 Correct 338 ms 852 KB Output is correct

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 531 ms 852 KB Output isn't correct
2 Correct 533 ms 860 KB Output is correct

Subtask #3
15.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 856 KB Output is correct
2 Incorrect 880 ms 868 KB Output isn't correct
3 Correct 907 ms 856 KB Output is correct
4 Incorrect 938 ms 972 KB Output isn't correct
5 Correct 999 ms 856 KB Output is correct

Subtask #4
25.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1722 ms 852 KB Output isn't correct
2 Correct 1844 ms 852 KB Output is correct
3 Incorrect 2048 ms 860 KB Output isn't correct
4 Correct 2109 ms 864 KB Output is correct
5 Incorrect 2246 ms 856 KB Output isn't correct
6 Correct 2308 ms 860 KB Output is correct
7 Incorrect 2437 ms 860 KB Output isn't correct
8 Correct 2446 ms 856 KB Output is correct
9 Incorrect 2402 ms 852 KB Output isn't correct
10 Correct 2457 ms 872 KB Output is correct