Submission #241475

#	Time	Username	Problem	Language	Result	Execution time	Memory
241475		mosesmayer	Vision Program (IOI19_vision)	C++17	59 / 100	47 ms	4084 KiB

vision

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

using namespace std;

int GH, GW;
int coord(int i, int j) {
	return i * GW + j;
};

void construct_network(int H, int W, int K) {
	tie(GH, GW) = {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
		//add left diagonals
		for (int sum = 0; sum <= H + W - 2; sum++){
			vector<int> tmp;
			for (int r = 0, c = sum; c >= 0 && r < H; r++, c--){
				if (c < W) {
					tmp.push_back(coord(r, c));
				}
			}
			if (tmp.empty()) continue;
//			printf("add left squares: ");
//			for (int i : tmp) {
//				printf("{%d, %d} ", i / W, i % W);
//			}
//			puts("");
			left_diags_or.push_back(add_or(tmp));
			left_diags_xor.push_back(add_xor(tmp));
		}

		//add right diagonals
		for (int diff = -H + 1; diff <= W; diff++) {
			vector<int> tmp;
			for (int r = H - 1, c = H - 1 + diff; r >= 0; r--, c--) {
				if (0 <= c && c < W) {
					tmp.push_back(coord(r, c));
				}
			}
			if (tmp.empty()) continue;
//			printf("add right squares: ");
//			for (int i : tmp) {
//				printf("{%d, %d} ", i / W, i % W);
//			}
//			puts("");
			right_diags_or.push_back(add_or(tmp));
			right_diags_xor.push_back(add_xor(tmp));
		}
	//

	// 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.
	//puts("start diags2");
	vector<int> left_diags_has2, right_diags_has2;
	for (int i = 0, sz = left_diags_or.size(); i < sz; i++){
		vector<int> curr = {left_diags_or[i], left_diags_xor[i]};
		left_diags_has2.push_back(add_xor(curr));
	}
	for (int i = 0, sz = right_diags_or.size(); i < sz; i++){
		vector<int> curr = {right_diags_or[i], right_diags_xor[i]};
		right_diags_has2.push_back(add_xor(curr));
	}
	//puts("add 2diags done");

	vector<int> left_k1, right_k1;
	for (int i = 0, j = K, sz = left_diags_has2.size(); j < sz; i++, j++){
		vector<int> curr;
		for (int x = i; x <= j; x++) {
			curr.push_back(left_diags_has2[x]);
		}
		int has2samecol = add_or(curr);
		curr.clear();
		for (int x = i; x <= j; x++){
			curr.push_back(left_diags_or[x]);
		}
		int has2difcol = add_xor({add_or(curr), add_xor(curr)});
		left_k1.push_back(add_or({has2samecol, has2difcol}));
	}
	for (int i = 0, j = K, sz = right_diags_has2.size(); j < sz; i++, j++){ vector<int> curr;
		for (int x = i; x <= j; x++) {
			curr.push_back(right_diags_has2[x]);
		}
		int has2samecol = add_or(curr);
		curr.clear();
		for (int x = i; x <= j; x++){
			curr.push_back(right_diags_or[x]);
		}
		int has2difcol = add_xor({add_or(curr), add_xor(curr)});
		right_k1.push_back(add_or({has2samecol, has2difcol}));
	}
	int k1val = add_and({add_or(left_k1), add_or(right_k1)});
	//puts("k1 done");


	vector<int> left_k, right_k;
	for (int i = 0, j = K - 1, sz = left_diags_has2.size(); j < sz; i++, j++){
		vector<int> curr;
		for (int x = i; x <= j; x++) {
			curr.push_back(left_diags_has2[x]);
		}
		int has2samecol = add_or(curr);
		curr.clear();
		for (int x = i; x <= j; x++){
			curr.push_back(left_diags_or[x]);
		}
		int has2difcol = add_xor({add_or(curr), add_xor(curr)});
		left_k.push_back(add_or({has2samecol, has2difcol}));
	}
	for (int i = 0, j = K - 1, sz = right_diags_has2.size(); j < sz; i++, j++){ vector<int> curr;
		for (int x = i; x <= j; x++) {
			curr.push_back(right_diags_has2[x]);
		}
		int has2samecol = add_or(curr);
		curr.clear();
		for (int x = i; x <= j; x++){
			curr.push_back(right_diags_or[x]);
		}
		int has2difcol = add_xor({add_or(curr), add_xor(curr)});
		right_k.push_back(add_or({has2samecol, has2difcol}));
	}
	int kval = add_and({add_or(left_k), add_or(right_k)});
	//puts("k done");

	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: 0 / 8
• Subtask 7: 0 / 14
• Subtask 8: 0 / 19