fork(5) download
copy 
  1. #include <iostream>
  2. #include <memory>
  3. #include <vector>
  4.  
  5. static const uint64_t SEED = 0xDEADBEEFull;
  6. static const size_t ROWS = 10000;
  7. static const size_t COLS = 10000;
  8. static const uint32_t COLORS_NUM = 3;
  9.  
  10. uint32_t LCGRand()
  11. {
  12.     static uint64_t seed = SEED;
  13.     seed = seed * 6364136223846793005 + 1442695040888963407;
  14.     return seed >> 32;
  15. }
  16.  
  17. struct Block {
  18. 	typedef std::shared_ptr<Block> Ptr;
  19.  
  20. 	uint32_t color;
  21. 	size_t size;
  22. 	Ptr redir;
  23. };
  24.  
  25. int main()
  26. {
  27. 	std::vector<Block::Ptr> up_row(COLS);
  28. 	size_t max_size = 0;
  29.  
  30.     for (size_t row = 0; row < ROWS; row++) {
  31.     	Block::Ptr left;
  32.  
  33.     	for (size_t col = 0; col < COLS; col++) {
  34.     		uint32_t color = LCGRand() % COLORS_NUM;
  35.  
  36.     		Block::Ptr &up = up_row[col];
  37.     		while (up && up->redir)
  38.     			up = up->redir;
  39.  
  40.     		Block::Ptr cur;
  41.     		if (left && (left->color == color)) {
  42.     			cur = left;
  43.  
  44.     			if (up && (up->color == color) && (up != left)) {
  45.     				left->size += up->size;
  46.     				up->redir = left;
  47.     			}
  48.     		} else if (up && (up->color == color)) {
  49.     			cur = up;
  50.     		} else {
  51.     			cur = std::make_shared<Block>(Block{color, 0, nullptr});
  52.     		}
  53.  
  54.     		max_size = std::max(max_size, ++cur->size);
  55.     		left = up = cur;
  56.     	}
  57.     }
  58.  
  59.     std::cout << "Max block size: " << max_size << std::endl;
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 4.88s 4220KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max block size: 93
https://ideone.com/kKEyGB
language:
C++14 (gcc 8.3)
created:
4 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!