#include <iostream>
#include <fstream>
#include <chrono>
#include <vector>
#include <thread>

using namespace std;

constexpr int mapSize = 16384;

constexpr inline size_t clampLow(size_t rowOrCol) {
	if (rowOrCol < 500) return 0;
	return rowOrCol - 500;
}

constexpr inline size_t clampHigh(size_t rowOrCol) {
	if (rowOrCol >= mapSize - 500) return mapSize;
	return rowOrCol + 500 + 1;
}

template<typename T = uint16_t>
T** createMap(T* array) {
	T** map = new T * [mapSize];
	for (size_t i = 0; i < mapSize; i++) {
		map[i] = array + i * mapSize;
	}
	return map;
}

void output(ostream& out, const vector<pair<size_t, size_t>>& chosen) {
	out << chosen.size() << endl;
	for (const auto& i : chosen) {
		out << i.first << " " << i.second << endl;
	}
}

int totalPrice = 0;
int bought = 0;

template<typename T = uint16_t>
void buy(T** map, size_t row, size_t col, bool countToTotal = true) {
	if (countToTotal) {
		++bought;
		totalPrice += map[row][col];
	}

	const size_t rmin = clampLow(row);
	const size_t cmin = clampLow(col);
	const size_t rmax = clampHigh(row);
	const size_t cmax = clampHigh(col);
	for (size_t r = rmin; r < rmax; r++) {
		for (size_t c = cmin; c < cmax; c++) {
			map[r][c] = 0;
		}
	}
}

//#define dontUsePrice
long long countCoveredBy(uint16_t** map, size_t rmin, size_t rmax, size_t cmin, size_t cmax) {
	long long count = 0;
	for (size_t r = rmin; r < rmax; r++) {
		for (size_t c = cmin; c < cmax; c++) {
#ifdef dontUsePrice
			if (map[r][c]) ++count;
#else
			count += map[r][c];
#endif
		}
	}
	return count;
}

constexpr inline bool isBetter(size_t newPrice, long long newCover, size_t oldPrice, long long oldCover) {
#ifdef dontUsePrice
	constexpr int mult = 1;
#else
	constexpr int mult = 0x00072000;// best: 0x00072000
#endif
	return ((long long)newCover - (long long)newPrice * mult > (long long)oldCover - (long long)oldPrice * mult);
}

pair<size_t, size_t> chooseBest(uint16_t** map, size_t rmin, size_t rmax, size_t cmin, size_t cmax) {
	long long max = 0;
	size_t price = 0xffff;
	size_t chr = 0, chc = 0;

	size_t cols = cmax - cmin;
	size_t rows = rmax - rmin;
	long long* counts = new long long[cols];

	const size_t rminPlus500 = clampHigh(rmin);
	counts[0] = countCoveredBy(map, rmin, rminPlus500, clampLow(cmin), clampHigh(cmin));
	if (map[rmin][cmin]) {
		max = counts[0];
		price = map[rmin][cmin];
	}

	for (size_t c = 1; c < cols; c++) {
		counts[c] = counts[c - 1];
		if (cmin + c >= 500) counts[c] -= countCoveredBy(map, rmin, rminPlus500, cmin + c - 500, cmin + c - 500 + 1);
		if (cmin + c < mapSize - 500) counts[c] += countCoveredBy(map, rmin, rminPlus500, cmin + c + 500, cmin + c + 500 + 1);

		if (map[rmin][cmin + c] && isBetter(map[rmin][cmin + c], counts[c], price, max)) {
			max = counts[c];
			price = map[rmin][cmin + c];
			chc = c;
		}
	}

	for (size_t r = 1; r < rows; r++) {
		long long prev = counts[0];
		if (rmin + r >= 500) counts[0] -= countCoveredBy(map, rmin + r - 500, rmin + r - 500 + 1, clampLow(cmin), clampHigh(cmin));
		if (rmin + r < mapSize - 500) counts[0] += countCoveredBy(map, rmin + r + 500, rmin + r + 500 + 1, clampLow(cmin), clampHigh(cmin));

		for (size_t c = 1; c < cols; c++) {
			long long diff = counts[c] - prev;
			prev = counts[c];
			counts[c] = counts[c - 1] + diff;
			if (cmin + c >= 500) {
				if (rmin + r >= 500) counts[c] += countCoveredBy(map, rmin + r - 500, rmin + r - 500 + 1, cmin + c - 500, cmin + c - 500 + 1);
				if (rmin + r < mapSize - 500) counts[c] -= countCoveredBy(map, rmin + r + 500, rmin + r + 500 + 1, cmin + c - 500, cmin + c - 500 + 1);
			}
			if (cmin + c < mapSize - 500) {
				if (rmin + r >= 500) counts[c] -= countCoveredBy(map, rmin + r - 500, rmin + r - 500 + 1, cmin + c + 500, cmin + c + 500 + 1);
				if (rmin + r < mapSize - 500) counts[c] += countCoveredBy(map, rmin + r + 500, rmin + r + 500 + 1, cmin + c + 500, cmin + c + 500 + 1);
			}
			if (map[rmin + r][cmin + c] && isBetter(map[rmin + r][cmin + c], counts[c], price, max)) {
				max = counts[c];
				price = map[rmin + r][cmin + c];
				chr = r;
				chc = c;
			}
		}
	}

	delete[] counts;

	chr += rmin;
	chc += cmin;
	return { chr, chc };
}

void run(uint16_t* prague, ostream& out) {
	uint16_t** map = createMap(prague);

	vector<pair<size_t, size_t>> chosen;

	for (size_t r = 0; r < mapSize; r++) {
		if (!(r & 0xff)) cout << "Row " << r << endl;
		for (size_t c = 0; c < mapSize; c++) {
			if (map[r][c]) {
				auto choice = chooseBest(map, r, clampHigh(r), clampLow(c), clampHigh(c));
				buy(map, choice.first, choice.second);
				chosen.push_back(choice);
			}
		}
	}

	delete[] map;

	output(out, chosen);
}

void initPrague(const char* buffer, uint16_t* prague, size_t count) {
	for (size_t i = 0; i < count; i++) {
		prague[i] = (uint16_t)(unsigned char)buffer[i * 2] | ((uint16_t)(unsigned char)buffer[i * 2 + 1] << 8);
	}
}

void loadPrague(const char* file, uint16_t* prague, size_t offset, size_t count) {
	ifstream in(file, ios::binary);
	in.seekg(static_cast<std::streamsize>(offset) * 2);

	char* buffer = new char[count * 2];
	in.read(buffer, static_cast<std::streamsize>(count) * 2);

	initPrague(buffer, prague + offset, count);

	delete[] buffer;
}

uint16_t* load(const char* file) {
	uint16_t* prague = new uint16_t[mapSize * mapSize];

	constexpr int section = mapSize * mapSize / 4;

	thread t1(loadPrague, file, prague, 0, section);
	thread t2(loadPrague, file, prague, section, section);
	thread t3(loadPrague, file, prague, section * 2, section);
	thread t4(loadPrague, file, prague, section * 3, section);
	t1.join();
	t2.join();
	t3.join();
	t4.join();

	return prague;
}

int main() {
	chrono::steady_clock c;
	auto start = c.now();

	uint16_t* prague = load("Prague.in");
	ofstream out("Prague.out");

	run(prague, out);

	cout << "Bought " << bought << " for " << totalPrice << endl;

	delete[] prague;

	auto end = c.now();

	cout << "Duration: " << chrono::duration_cast<chrono::seconds>(end - start).count() << " seconds";

	return 0;
}