Submission #241605

#	Time	Username	Problem	Language	Result	Execution time	Memory
241605		mosesmayer	Vision Program (IOI19_vision)	C++17	100 / 100	65 ms	5496 KiB

vision

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

using namespace std;

int H, W;
int coord(int i, int j) {
	return i * W + j;
};

vector<int> get_cells(int D, bool dir) {
	// dir is 1 if left diagonal (sum), 0 if right diagonal.
	vector<int> res;
	int start, stop, diff;
	if (dir) {
		start = D < W ? D : (D - W + 1) * W + (W - 1);
		stop = D < H ? D * W : (H - 1) * W + (D - H + 1);
		diff = W - 1;
	} else {
		start = D < W ? W - 1 - D : (D - W + 1) * W;
		stop = D < H ? (D + 1) * W - 1 : H * W - 1 - (D - H + 1);
		diff = W + 1;
	}
	for (; start <= stop; start += diff) {
		res.emplace_back(start);
		if (start == stop) break;
	}
	return res;
}

void construct_diagonals(bool dir, vector<int>& orv, vector<int>& xorv) {
	for (int i = 0; i <= H + W - 2; i++) {
		vector<int> cur = get_cells(i, dir);
		// printf("add %s squares: ", dir ? "left" : "right");
		// for (int i : cur) {
		// 	printf("%d ", i);
		// }
		// puts("");
		orv.emplace_back(add_or(cur));
		xorv.emplace_back(add_xor(cur));
	}
}

int test(const vector<int>& orv, const vector<int>& xorv, int D) {
	// tests if there are D consecutive diagonals which has 2 black.
	vector<int> cur_or(D), cur_xor(D), res;
	for (int i = 0, t = orv.size(); i < t; i++) {
		cur_or[i % D] = orv[i];
		cur_xor[i % D] = xorv[i];
		if (i >= D - 1)
			res.emplace_back(add_and({add_or(cur_or),
					         add_not(add_xor(cur_xor)) // odd iff exactly 1.
			}));
	}
	return add_or(res);
}

void construct_network(int H, int W, int K) {
	tie(::H, ::W) = {H, W};
//	std::vector<int> Ns;
//	Ns = {0, 1};
//	int a = add_and(Ns);
//	Ns = {0, a};
//	int b = add_or(Ns);
//	Ns = {0, 1, b};
//	int c = add_xor(Ns);
//	add_not(c);

	vector<int> left_diags_or, right_diags_or;
	vector<int> left_diags_xor, right_diags_xor;

	// Base diagonal processing
	construct_diagonals(1, left_diags_or, left_diags_xor);
	construct_diagonals(0, right_diags_or, right_diags_xor);

	// or -> 1 if has black pixel in diag, 0 otherwise
	// xor -> if 0 where or is 1, then 2 black in diag. if 1 then 1 black.
	// if consecutive diagonals, if xor of xor's = 1 then exactly 1 black
	// if or of or's = 1 then >= 1 black.
	// if xor of xor's = 0 then even num of blacks.
	// want or of or's = 1 and xor of xor's = 0.

	int k1val = add_and({test(left_diags_or, left_diags_xor, K + 1),
						test(right_diags_or,right_diags_xor, K + 1)});
	int kval = add_and({test(left_diags_or, left_diags_xor, K),
						test(right_diags_or,right_diags_xor, K)});
	// want k1val true and kval false.
	add_and({k1val, add_xor({kval, k1val})});
}

• 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