Submission #1079700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079700		BestCrazyNoob	Vision Program (IOI19_vision)	C++17	100 / 100	11 ms	2004 KiB

vision

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

using namespace std;

constexpr int BITS = 9;					// ############## TODO ###############à //
using BITINT = array<int, BITS>;

BITINT createInt(int x, int zero, int one) {
	BITINT res;
	for (int h = 0; h < BITS; h++) {
		res[h] = (x & (1 << h)) ? add_or({one}) : add_or({zero});
	}
	return res;
}

BITINT doCreateInt(int x, int zero) {
	BITINT res;
	for (int h = 0; h < BITS; h++) {
		res[h] = (x & (1 << h)) ? add_not(zero) : add_or({zero});
	}
	return res;
}

BITINT orInt(vector<BITINT> v) {
	BITINT res;
	for (int h = 0; h < BITS; h++) {
		vector<int> vh;
		for (BITINT b: v) vh.push_back(b[h]);
		res[h] = add_or(vh);
	}
	return res;
}

BITINT addInt(BITINT a, BITINT b) {
	BITINT res;
	res[0] = add_xor({a[0], b[0]});
	int carry = add_and({a[0], b[0]});
	for (int h = 1; h < BITS; h++) {
		res[h] = add_xor({a[h], b[h], carry});
		carry = add_or({
			add_and({a[h], b[h]}),
			add_and({carry, add_xor({a[h], b[h]})}
		)});
	}
	return res;
}

int equal(BITINT a, BITINT b) {
	vector<int> _xor;
	for (int h = 0; h < BITS; h++) {
		_xor.push_back(add_xor({a[h], b[h]}));
	}
	return add_not(add_or(_xor));
}

void construct_network(int H, int W, int K) {
	auto get = [&](int i, int j) {
		return W*i + j;
	};

	int zero = add_and({0, add_not(0)});

	vector<int> rowOr, ySweep(H), rySweep(H);
	vector<BITINT> ys1(H), ys2(H);
	for (int i = 0; i < H; i++) {
		vector<int> Y;
		for (int j = 0; j < W; j++) Y.push_back(get(i, j));
		rowOr.push_back(add_or(Y));
	}

	ySweep[0] = add_or({rowOr[0]});
	ys1[0] = createInt(0, zero, ySweep[0]);
	for (int i = 1; i < H; i++) {
		ySweep[i] = add_or({rowOr[i], ySweep[i-1]});
		ys1[i] = createInt(i, zero, add_xor({ySweep[i-1], ySweep[i]}));
	}

	rySweep[H-1] = add_or({rowOr[H-1]});
	ys2[H-1] = createInt(H-1, zero, rySweep[H-1]);
	for (int i = H-2; i >= 0; i--) {
		rySweep[i] = add_or({rowOr[i], rySweep[i+1]});
		ys2[i] = createInt(i, zero, add_xor({rySweep[i+1], rySweep[i]}));
	}

	vector<int> colOr, xSweep(W), rxSweep(W);
	vector<BITINT> xs1(W), xs2(W);
	for (int j = 0; j < W; j++) {
		vector<int> Y;
		for (int i = 0; i < H; i++) Y.push_back(get(i, j));
		colOr.push_back(add_or(Y));
	}

	xSweep[0] = add_or({colOr[0]});
	xs1[0] = createInt(0, zero, xSweep[0]);
	for (int j = 1; j < W; j++) {
		xSweep[j] = add_or({colOr[j], xSweep[j-1]});
		xs1[j] = createInt(j, zero, add_xor({xSweep[j-1], xSweep[j]}));
	}

	rxSweep[W-1] = add_or({colOr[W-1]});
	xs2[W-1] = createInt(W-1, zero, rxSweep[W-1]);
	for (int j = W-2; j >= 0; j--) {
		rxSweep[j] = add_or({colOr[j], rxSweep[j+1]});
		xs2[j] = createInt(j, zero, add_xor({rxSweep[j+1], rxSweep[j]}));
	}

	BITINT y1 = orInt(ys1);
	BITINT y2 = orInt(ys2);
	BITINT x1 = orInt(xs1);
	BITINT x2 = orInt(xs2);

	equal(addInt(addInt(x1, y1), doCreateInt(K, zero)), addInt(x2, y2));
}

• 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