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