#include <bits/stdc++.h>
#include "message.h"

using namespace std;

int arr[31];

namespace help{
	int message[31][66];
}

void send_message(std::vector<bool> M, std::vector<bool> C) {
	int p = -1;
	int f = -1;
	memset(arr, 0, sizeof(int) * 31);
	memset(help::message, -1, sizeof(int) * 31*66);
	for (int x = 0; x < 31; x ++){
		if (!C[x]){
			if (f == -1){
				p = x;
				f = x;
			}else {
				arr[p] = x-p;
				p = x;
			}
		}
	}
	arr[p] = 31+f - p;
	for (int x = 0; x < 31; x ++){
		if (!C[x]){
			// do elias omega coding
			std::vector<int> res;
			res.push_back(0);
			int v = arr[x];
			while (v != 1){
				res.push_back(v);
				v = 31-__builtin_clz(v);
			}
			reverse(res.begin(), res.end());
			int ind = 0;
			for (int v: res){
				if (v == 0){
					help::message[x][ind++] = 0;
				}else {
					for (int i = 31-__builtin_clz(v); i >= 0; i --){
						help::message[x][ind++] = (v & (1 << i)) > 0;
					}
				}
			}
		}
	}
	std::vector<std::array<int, 2>> sizeW;
	int ind = 0;
	int pack = 0;
	for (int y = 0; y < 66; y ++){
		for (int x = 0; x < 31; x ++){
			if (C[x]) continue;
			if (help::message[x][y] != -1){
				pack = y;
				continue;
			}
			if (sizeW.size() < 10){
				sizeW.push_back({x, y});
				help::message[x][y] = -2;
			}else if (ind < (int)M.size()){
				help::message[x][y] = M[ind++];
				pack = x;
			}
		}
	}
	pack ++;
	/*
	for (int y = 0; y < 66; y ++){
		for (int x = 0; x < 31; x ++){
			printf("%2d ", help::message[x][y]);
		}
		cout << endl;
	}
	*/
	assert(ind == (int)M.size());
	for (int x = 0; x < 10; x ++){
		help::message[sizeW[x][0]][sizeW[x][1]] = (bool)((M.size()-1) & (1 << x));
	}
	for (int y = 0; y < pack; y ++){
		std::vector<bool> res;
		for (int x = 0; x < 31; x ++){
			res.push_back((bool)help::message[x][y]);
		}
		send_packet(res);
	}
}

int decodeElias(int i, int s){
	int N = 1;
	int ind = 0;
	while (help::message[i][ind] != 0){
		int v = 0;
		for (int x = 0; x <= N; x ++){
			int val = help::message[i][ind];
			help::message[i][ind ++] = -2;
			if (ind >= 12 || ind >= s){
				return 0;
			}
			v <<= 1;
			v += val;
			//v += val << x;
		}
		N = v;
	}
	help::message[i][ind ++] = -2;
	return N;
}

namespace check{

int good[31];
int time[31];

void dfs(int i, int t = 1){
	if (good[i] != 0){
		return;
	}
	if (time[i] != 0){
		if (t - time[i] == 16){
			good[i] = 1;
			dfs((arr[i] + i) % 31, t+1);
			return;
		}else {
			good[i] = -1;
			return;
		}
	}
	time[i] = t;
	dfs((arr[i] + i) % 31, t+1);
	if (good[i] == 0){
		good[i] = -1;
	}
}

}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
	memset(arr, 0, sizeof(int) * 31);
	memset(check::good, 0, sizeof(int) * 31);
	memset(help::message, -1, sizeof(int) * 31*66);
	memset(check::time, 0, sizeof(int) * 31);
	for (int y = 0; y < (int)R.size(); y ++){
		for (int x = 0; x < 31; x ++){
			help::message[x][y] = R[y][x];
			//cout << help::message[x][y] << " ";
		}
		//cout << endl;
	}
	for (int x = 0; x < 31; x ++){
		arr[x] = decodeElias(x, R.size());
		//cout << arr[x] << " ";
	}
	//cout << endl;

	for (int x = 0; x < 31; x ++){
		if (check::good[x] != 0){
			continue;
		}
		check::dfs(x);
	}

	int totLen = 0;
	int i = 0;
	std::vector<bool> res;
	for (int y = 0; y < (int)R.size(); y ++){
		for (int x = 0; x < 31; x ++){
			if (check::good[x] == 1){
				if (help::message[x][y] == -2){
					continue;
				}
				if (i < 10){
					totLen += (int)help::message[x][y] << (i ++);
				}else {
					if (res.empty()){
						totLen ++;
					}
					if ((int)res.size() < totLen){
						res.push_back(help::message[x][y]);
					}
				}
			}
		}
	}

	return res;
}