fork(4) download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <memory>
  4. #include <vector>
  5. #include <ctime>
  6.  
  7. static const uint64_t SEED = 0xDEADBEEFull;
  8. static const size_t ROWS = 10000;
  9. static const size_t COLS = 10000;
  10. static const uint32_t COLORS_NUM = 3;
  11.  
  12. uint32_t LCGRand()
  13. {
  14.     static uint64_t seed = SEED;
  15.     seed = seed * 6364136223846793005 + 1442695040888963407;
  16.     return seed >> 32;
  17. }
  18.  
  19. struct Node {
  20. 	uint32_t color;
  21. 	size_t size;
  22. 	Node *next;
  23. 	Node *prev;
  24.  
  25. 	Node() : color(COLORS_NUM), size(0), next(this), prev(this) { }
  26.  
  27. 	void PushOut(size_t& max_size) {
  28. 		if (next == this) {
  29. 			max_size = std::max(max_size, size);
  30. 			return;
  31. 		}
  32. 		next->size += size;
  33. 		next->prev = prev;
  34. 		prev->next = next;
  35. 		next = prev = this;
  36. 	}
  37.  
  38. 	void LinkTo(Node &other) {
  39. 		other.prev->next = next;
  40. 		next->prev = other.prev;
  41. 		next = &other;
  42. 		other.prev = this;
  43. 	}
  44. };
  45.  
  46. int main()
  47. {
  48. 	std::vector<Node> scanline(COLS);
  49.  
  50. 	size_t max_size = 0;
  51.  
  52. 	clock_t start = clock();
  53.  
  54.     for (size_t row = 0; row < ROWS; row++) {
  55.     	for (size_t col = 0; col < COLS; col++) {
  56.     		uint32_t color = LCGRand() % COLORS_NUM;
  57.  
  58.     		if (scanline[col].color != color) {
  59.     			scanline[col].PushOut(max_size);
  60.     			scanline[col].color = color;
  61.     			scanline[col].size = 1;
  62.     		} else {
  63.     			scanline[col].size++;
  64.     		}
  65.  
  66.     		if ((col > 0) && (scanline[col - 1].color == color))
  67.     			scanline[col].LinkTo(scanline[col - 1]);
  68.     	}
  69.     }
  70.  
  71.     for (size_t col = 0; col < COLS; col++)
  72.     	scanline[col].PushOut(max_size);
  73.  
  74.     std::cout << "Max block size: " << max_size << std::endl;
  75.     std::cout << "Time: " << (clock() - start) / (CLOCKS_PER_SEC / 1000) << " ms" << std::endl;
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0.9s 4312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max block size: 93
Time: 894 ms
https://ideone.com/k37NrX
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!