fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. #define LIMIT 10000000 /*size of integers array*/
  6. #define PRIMES 700000 /*size of primes array*/
  7. #define    N	351
  8. int numbers[LIMIT];// numbers[i] is -1 if it is not prime otherwise numbers[i] = i+2
  9. int primes[PRIMES];// list of prime numbers 2,3,5,7...
  10. int a[N][N]; // passwords of server[i][j]
  11. bool b[N][N]; // is true if b[i][j] has been cracked by grid hacking mechanism
  12. bool even[N][N];// even[i][j] = true if password of server is nonprime even, otherwise false
  13. bool odd[N][N];// odd[i][j] = true if password of server is nonprime odd, otherwise false
  14. bool memo1[N][N];// return true when memo1[i][j] has been visited once in grid hacking mechanism of even numbers function
  15. bool memo2[N][N];// return true when memo2[i][j] has been visited once in grid hacking mechanism of odd numbers function
  16.  
  17. int bSearch(int x, int low, int high){
  18.     int mid;
  19.     while (low <= high) {
  20.     	mid = (low + high) / 2;
  21.     	if (x < primes[mid])
  22.     		high = mid - 1;
  23.     	else if (x > primes[mid])
  24.     		low = mid + 1;
  25.     	else
  26.     		return mid;
  27.     }
  28.     return -1;
  29. }
  30. void gridhackeven(int i, int j, int n) {
  31. 	if (memo1[i][j] == true)
  32. 		return;
  33. 	memo1[i][j] = true;
  34. 	b[i][j] = true;
  35. 	if (j+1 <= n-1 && even[i][j+1] == true) {
  36. 		b[i][j+1] = true;
  37. 		gridhackeven(i,j+1,n);
  38. 	}
  39. 	if (j-1 >= 0 && even[i][j-1] == true) {
  40. 		b[i][j-1] = true;
  41. 		gridhackeven(i,j-1,n);
  42. 	}
  43. 	if (i-1 >= 0 && even[i-1][j] == true) {
  44. 		b[i-1][j] = true;
  45. 		gridhackeven(i-1,j,n);
  46. 	}
  47. 	if (i+1 <= n-1 && even[i+1][j] == true) {
  48. 		b[i+1][j] = true;
  49. 		gridhackeven(i+1,j,n);
  50. 	}
  51. 	return;
  52. }
  53. void gridhackodd(int i, int j, int n) {
  54. 	if (memo2[i][j] == true)
  55. 		return;
  56. 	memo2[i][j] = true;
  57. 	b[i][j] = true;
  58. 	if (j+1 <= n-1 && odd[i][j+1] == true) {
  59. 		b[i][j+1] = true;
  60. 		gridhackodd(i,j+1,n);
  61. 	}
  62. 	if (j-1 >= 0 && odd[i][j-1] == true) {
  63. 		b[i][j-1] = true;
  64. 		gridhackodd(i,j-1,n);
  65. 	}
  66. 	if (i-1 >= 0 && odd[i-1][j] == true) {
  67. 		b[i-1][j] = true;
  68. 		gridhackodd(i-1,j,n);
  69. 	}
  70. 	if (i+1 <= n-1 && odd[i+1][j] == true) {
  71. 		b[i+1][j] = true;
  72. 		gridhackodd(i+1,j,n);
  73. 	}
  74. 	return;
  75. }		
  76. inline void scan(int *a) {
  77. 	register char c=0;
  78. 	while (c < 33)
  79. 		c = getchar_unlocked();
  80. 	*a = 0;	
  81. 	while (c > 33) {
  82. 		*a = *a * 10 + c - '0';
  83. 		c = getchar_unlocked();
  84. 	}
  85. }
  86.  
  87. int main(){
  88.     int i,j;
  89.  
  90.     /*fill the array with natural numbers*/
  91.     for (i=0;i<LIMIT;i++){
  92.         numbers[i]=i+2;
  93.     }
  94.  
  95.     /*sieve the non-primes*/
  96.     for (i=0;i<LIMIT;i++){
  97.         if (numbers[i]!=-1){
  98.             for (j=2*numbers[i]-2;j<LIMIT;j+=numbers[i])
  99.                 numbers[j]=-1;
  100.         }
  101.     }
  102.     j = 0;
  103.     for (i=0;i<LIMIT&&j<PRIMES;i++)
  104.         if (numbers[i]!=-1)
  105.             primes[j++] = numbers[i];
  106.  
  107. 	int limit = j;
  108. 	int t, n;
  109. 	long long count;
  110. 	scan(&t);
  111. 	while (t--) {
  112. 		scan(&n);
  113. 		for (i = 0; i < n; i++) {
  114. 			for (j = 0; j < n; j++) {
  115. 				scan(&a[i][j]);
  116. 				b[i][j] = false;
  117. 				memo1[i][j] = false;
  118. 				memo2[i][j] = false;
  119. 				even[i][j] = false;
  120. 				odd[i][j] = false;
  121. 				if (numbers[a[i][j]-2] == -1) {
  122. 					if (a[i][j] % 2 == 0) {
  123. 						even[i][j] = true;
  124. 						odd[i][j] = false;
  125. 					}
  126. 					else {
  127. 						odd[i][j] = true;
  128. 						even[i][j] = false;
  129. 					}
  130. 				}
  131. 			}
  132. 		}
  133. 		count = 0;
  134. 		for (i = 0; i < n; i++) {
  135. 			for (j = 0; j < n; j++) {
  136. 				if (b[i][j] != true) {
  137. 					if (numbers[a[i][j]-2] != -1) {
  138. 						b[i][j] = true;
  139. 						count += bSearch(a[i][j],0,limit-1);
  140. 					}	
  141. 					else if (even[i][j] == true) {
  142. 						count += (a[i][j]>>1);
  143. 						gridhackeven(i, j, n);
  144. 					}
  145. 					else if(odd[i][j] == true) {
  146. 						count += ((a[i][j]+1)>>1) +1;
  147. 						gridhackodd(i, j, n);
  148. 					}
  149. 				}
  150. 			}
  151. 		}
  152. 		printf("%lld\n", count);
  153. 	}
  154.  
  155. 	return 0;
  156. }
Success #stdin #stdout 0.67s 44560KB
comments (?)
stdin
copy 
2
3
2 6 4
4 8 9
7 9 4
2
8 4
15 4
stdout
copy 
20
13
https://ideone.com/6XWyVR
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!