#include <iostream>
#include <iomanip>
#include <memory>
#include <vector>
#include <ctime>

static const uint64_t SEED = 0xDEADBEEFull;
static const size_t ROWS = 10000;
static const size_t COLS = 10000;
static const uint32_t COLORS_NUM = 3;

uint32_t LCGRand()
{
    static uint64_t seed = SEED;
    seed = seed * 6364136223846793005 + 1442695040888963407;
    return seed >> 32;
}

struct Node {
	uint32_t color;
	size_t size;
	Node *next;
	Node *prev;
	
	Node() : color(COLORS_NUM), size(0), next(this), prev(this) { }
	
	void PushOut(size_t& max_size) {
		if (next == this) {
			max_size = std::max(max_size, size);
			return;
		}
		next->size += size;
		next->prev = prev;
		prev->next = next;
		next = prev = this;
	}
	
	void LinkTo(Node &other) {
		other.prev->next = next;
		next->prev = other.prev;
		next = &other;
		other.prev = this;
	}
};

int main()
{
	std::vector<Node> scanline(COLS);
	
	size_t max_size = 0;
	
	clock_t start = clock();
	
    for (size_t row = 0; row < ROWS; row++) {
    	for (size_t col = 0; col < COLS; col++) {
    		uint32_t color = LCGRand() % COLORS_NUM;
    		
    		if (scanline[col].color != color) {
    			scanline[col].PushOut(max_size);
    			scanline[col].color = color;
    			scanline[col].size = 1;
    		} else {
    			scanline[col].size++;
    		}
    		
    		if ((col > 0) && (scanline[col - 1].color == color))
    			scanline[col].LinkTo(scanline[col - 1]);
    	}
    }
    
    for (size_t col = 0; col < COLS; col++)
    	scanline[col].PushOut(max_size);
	
    std::cout << "Max block size: " << max_size << std::endl;
    std::cout << "Time: " << (clock() - start) / (CLOCKS_PER_SEC / 1000) << " ms" << std::endl;
    return 0;
}