Submission #831101

#	Time	Username	Problem	Language	Result	Execution time	Memory
831101		PurpleCrayon	Vision Program (IOI19_vision)	C++17	100 / 100	17 ms	2572 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;

void construct_network(int H, int W, int K) {
	if (H * W == 2) {
		add_or({0, 1});
		return;
	}

	int cur_cell = H * W;
	vector<int> base_h(H);
	for (int i = 0; i < H; i++) {
		vector<int> cur;
		for (int j = 0; j < W; j++) {
			cur.push_back(i * W + j);
		}

		add_or(cur);
		base_h[i] = cur_cell++;
	}

	vector<int> base_w(W);
	for (int j = 0; j < W; j++) {
		vector<int> cur;
		for (int i = 0; i < H; i++) {
			cur.push_back(i * W + j);
		}

		add_or(cur);
		base_w[j] = cur_cell++;
	}

	int z = cur_cell++;
	add_and({0, 1, 2});

	const int B = 9;
	vector<int> loc(B);
	for (int i = 0; i < B; i++) {
		add_and({z}); // pad with zeroes
		loc[i] = cur_cell++;
	}

	auto increment = [&](int carry) {
		for (int i = 0; i < B; i++) {
			int old_loc = loc[i];
			// cerr << carry << ' ' << loc[i] << ' ' << cur_cell << endl;

			loc[i] = cur_cell++;
			add_xor({old_loc, carry});
			
			add_and({carry, old_loc});
			carry = cur_cell++;
		}
	};

	for (int i = 0; i < H; i++) {
		vector<int> l, r;
		for (int j = 0; j < H; j++) {
			if (j <= i) l.push_back(base_h[j]);
			if (j >= i) r.push_back(base_h[j]);
		}

		int l_q = cur_cell++;
		add_or(l);

		int r_q = cur_cell++;
		add_or(r);

		int res = cur_cell++;
		add_and({l_q, r_q});
		increment(res);
	}

	for (int i = 0; i < W; i++) {
		vector<int> l, r;
		for (int j = 0; j < W; j++) {
			if (j <= i) l.push_back(base_w[j]);
			if (j >= i) r.push_back(base_w[j]);
		}

		int l_q = cur_cell++;
		add_or(l);

		int r_q = cur_cell++;
		add_or(r);

		int res = cur_cell++;
		add_and({l_q, r_q});
		increment(res);
	}

	K += 2;
	int ans_cell = z;
	for (int i = 0; i < B; i++) {
		int need = (K >> i) & 1;
		if (need) {
			// bad if loc[i] is a 0
			// or with not loc[i]
			int tmp = cur_cell++;
			add_not(loc[i]);

			add_or({ans_cell, tmp});
			ans_cell = cur_cell++;
		} else {
			// bad if loc[i] is a 1
			add_or({ans_cell, loc[i]});
			ans_cell = cur_cell++;
		}
	}

	add_not(ans_cell);
}

• 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