Submission #169553

#	Time	Username	Problem	Language	Result	Execution time	Memory
169553		BessieTheCow	Vision Program (IOI19_vision)	C++17	100 / 100	12 ms	1404 KiB

vision

#include "vision.h"
#include <vector>

using namespace std;

constexpr int bits = 9;

int n, m, k, zero, one, rowor, color, rmax, rmin, cmax, cmin;

int flatten(int x, int y)
{
	return x * m + y;
}

int maxset(int begin, int ln, int startpos)
{
	add_or({ begin + ln - 1 });
	for (int i = 1, j = begin + ln - 2; i < ln; i++, j--)
	{
		add_or({ j, startpos + i - 1 });
	}
	for (int i = ln - 1; i >= 0; i--)
	{
		add_not({ startpos + i });
	}
	startpos += ln;
	for (int i = 0; i < ln - 1; i++)
	{
		add_and({ startpos + i + 1, begin + i });
	}
	add_and({ begin + ln - 1 });
	startpos += ln;
	return startpos;
}

int bwnot(int begin, int ln, int startpos)
{
	for (int i = 0; i < ln; i++)
	{
		add_not(begin + i);
	}
	return startpos;
}

int bwand(int begin1, int begin2, int ln, int startpos)
{
	for (int i = 0; i < ln; i++)
	{
		add_and({ begin1 + i, begin2 + i });
	}
	return startpos;
}

int bwor(int begin1, int begin2, int ln, int startpos)
{
	for (int i = 0; i < ln; i++)
	{
		add_or({ begin1 + i, begin2 + i });
	}
	return startpos;
}

int bwxor(int begin1, int begin2, int ln, int startpos)
{
	for (int i = 0; i < ln; i++)
	{
		add_xor({ begin1 + i, begin2 + i });
	}
	return startpos;
}

int bitindex(int begin, int ln, int startpos)
{
	for (int b = 0; b < bits; b++)
	{
		vector<int> inputs;
		inputs.reserve(ln / 2);
		for (int i = begin; i < begin + ln;)
		{
			if ((i - begin) & (1 << b))
			{
				inputs.push_back(i);
				i++;
			}
			else
			{
				i += 1 << b;
			}
		}
		if (inputs.empty())
		{
			add_xor({ 0, 0 });
		}
		else
		{
			add_or(inputs);
		}
	}
	return startpos;
}

int gate(int begin, int ln, int condition, int startpos)
{
	for (int i = 0; i < ln; i++)
	{
		add_and({ begin + i, condition });
	}
	return startpos;
}

int halfadder(int x1, int x2, int startpos)
{
	add_xor({ x1, x2 });
	add_and({ x1, x2 });
	return startpos;
}

int fulladder(int x1, int x2, int carry, int startpos)
{
	startpos = halfadder(x1, x2, startpos);
	add_and({ startpos, carry });
	add_xor({ startpos, carry });
	add_or({ startpos + 1, startpos + 2 });
	startpos += 3;
	return startpos;
}

int adder(int begin1, int begin2, int startpos)
{
	startpos = halfadder(begin1, begin2, startpos);
	vector<int> positions;
	positions.reserve(bits);
	positions.push_back(startpos);
	for (int i = 1; i < bits; i++)
	{
		startpos = fulladder(begin1 + i, begin2 + i, startpos + 1, startpos + 2);
		positions.push_back(startpos);
	}
	startpos += 2;
	for (int pos : positions)
	{
		add_or({ pos });
	}
	return startpos;
}

int increment(int begin, int startpos)
{
	startpos = halfadder(begin, one, startpos);
	vector<int> positions;
	positions.reserve(bits);
	positions.push_back(startpos);
	for (int i = 1; i < bits; i++)
	{
		startpos = halfadder(begin + i, startpos + 1, startpos + 2);
		positions.push_back(startpos);
	}
	startpos += 2;
	for (int pos : positions)
	{
		add_or({ pos });
	}
	return startpos;
}

int negator(int begin, int startpos)
{
	startpos = bwnot(begin, bits, startpos);
	startpos = increment(startpos, startpos + bits);
	return startpos;
}

int subtract(int begin1, int begin2, int startpos)
{
	startpos = negator(begin2, startpos);
	startpos = adder(startpos, begin1, startpos + bits);
	return startpos;
}

int allxor(int begin, int ln, int startpos)
{
	vector<int> inputs;
	inputs.reserve(ln);
	for (int i = 0; i < ln; i++)
	{
		inputs.push_back(begin + i);
	}
	add_xor(inputs);
	return startpos;
}

int compare(int begin, int x, int startpos)
{
	vector<int> inputs;
	for (int i = 0; i < bits; i++)
	{
		if (x & (1 << i))
		{
			inputs.push_back(add_or({ begin + i }));
		}
		else
		{
			inputs.push_back(add_not(begin + i));
		}
	}
	return add_and(inputs);
}

void construct_network(int N, int M, int K)
{
	n = N;
	m = M;
	k = K;
	zero = add_xor({ 0, 0 });
	one = add_not(zero);
	rowor = one + 1;
	color = rowor + n;
	for (int i = 0; i < n; i++)
	{
		vector<int> row;
		row.reserve(m);
		for (int j = 0; j < m; j++)
		{
			row.push_back(flatten(i, j));
		}
		add_or(row);
	}
	for (int j = 0; j < m; j++)
	{
		vector<int> col;
		col.reserve(n);
		for (int i = 0; i < n; i++)
		{
			col.push_back(flatten(i, j));
		}
		add_or(col);
	}
	int rmaxset = maxset(rowor, n, color + m);
	int cmaxset = maxset(color, m, rmaxset + n);
	int notrmaxset = bwnot(rmaxset, n, cmaxset + m);
	int notcmaxset = bwnot(cmaxset, m, notrmaxset + n);
	int rminset = bwand(rowor, notrmaxset, n, notcmaxset + m);
	int cminset = bwand(color, notcmaxset, m, rminset + n);
	int rmaxindex = bitindex(rmaxset, n, cminset + m);
	int cmaxindex = bitindex(cmaxset, m, rmaxindex + bits);
	int rminindex = bitindex(rminset, n, cmaxindex + bits);
	int cminindex = bitindex(cminset, m, rminindex + bits);
	int rdiff = subtract(rmaxindex, rminindex, cminindex + bits);
	int rxor = allxor(rowor, n, rdiff + bits);
	int rcond = add_not(rxor);
	rdiff = gate(rdiff, bits, rcond, rcond + 1);
	int cdiff = subtract(cmaxindex, cminindex, rdiff + bits);
	int cxor = allxor(color, m, cdiff + bits);
	int ccond = add_not(cxor);
	cdiff = gate(cdiff, bits, ccond, ccond + 1);
	int distance = adder(rdiff, cdiff, cdiff + bits);
	compare(distance, k, distance + bits);
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 15 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 19 / 19