fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. #define NMAX 4000
  5. #define INTS 125
  6.  
  7. const int nbits = sizeof(int)*8;
  8.  
  9. int
  10. onlyone(unsigned int *col, unsigned int *row, int n)
  11. {
  12. 	int bits;
  13. 	unsigned int bit, prod;
  14. 	bits = 0;
  15. 	for(int i = 0; i < n; i++) {
  16. 		prod = row[i] & col[i];
  17. 		if(prod == 0)
  18. 			continue;
  19. 		for(; prod != 0; prod >>= 1) {
  20. 			bit = prod & 1U;
  21. 			if(bit == 0U)
  22. 				continue;
  23. 			if(bits != 0)
  24. 				return 0;
  25. 			bits = 1;
  26. 		}
  27. 	}
  28. 	return bits;
  29. }
  30.  
  31. int
  32. main(int argc, char *argv[])
  33. {
  34. 	int bit, ints, n, count;
  35. 	unsigned int rows[NMAX][INTS];
  36. 	unsigned int cols[NMAX][INTS];
  37. 	char buf[NMAX+2];
  38.  
  39. 	std::memset(rows, 0, NMAX*INTS*sizeof(int));
  40. 	std::memset(cols, 0, NMAX*INTS*sizeof(int));
  41. 	std::memset(buf, 0, NMAX+2);
  42. 	std::cin.sync_with_stdio(false);
  43. 	std::cin >> n;
  44. 	std::cin.getline(buf, 0);
  45.  
  46. 	for(int i = 0; i < n; i++) {
  47. 		std::cin.getline(buf, n+1);
  48. 		for(int j = 0; j < n; j++) {
  49. 			bit = buf[j] - '0';
  50. 			rows[i][j/nbits] |= bit << j%nbits;
  51. 			cols[j][i/nbits] |= bit << i%nbits;
  52. 		}
  53. 	}
  54.  
  55. 	count = 0;
  56. 	ints = n/nbits + 1;
  57. 	if(ints > INTS)
  58. 		ints = INTS;
  59. 	for(int i = 0; i < n; i++)
  60. 		for(int j = 0; j < n; j++)
  61. 			count += onlyone(rows[i], cols[j], ints);
  62.  
  63. 	std::cout << count << std::endl;
  64.  
  65. 	return 0;
  66. }
Success #stdin #stdout 0s 7068KB
comments (?)
stdin
copy 
5
10010
11001
10100
11110
10100
stdout
copy 
11
https://ideone.com/D55Q6X
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!