Submission #836594

#	Time	Username	Problem	Language	Result	Execution time	Memory
836594		happypotato	Vision Program (IOI19_vision)	C++17	100 / 100	13 ms	1904 KiB

vision

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

void construct_network(int n, int m, int k) {
	if (n * m == 2) {
		add_and({0, 1});
		return;
	}
	const int ZERO = add_and({0, 1, 2});
	const int ONE = add_not(ZERO);
	function<int(void)> add_zero = [&]() -> int { return add_and({ZERO}); };
	function<int(void)> add_one = [&]() -> int { return add_and({ONE}); };

	function<int(int, int)> hash = [&](int x, int y) -> int {
		return x * m + y;
	};
	function<bool(int, int)> valid = [&](int x, int y) -> bool {
		return ((0 <= x && x < n) && (0 <= y && y < m));
	};
	
	// stores position of min in range [st, en]
	function<int(int, int)> findmin = [&](int st, int en) -> int {
		int diff = en - st + 1;
		int prev = add_zero();
		for (int i = 1; i < 8; i++) add_zero();
		vector<int> allprev;
		int prevtakexor = add_zero();
		for (int cur = 1; cur <= diff; cur++) { // from min
			int pos = st + (cur - 1);
			// check if [prev, prev + 8) has value
			vector<int> prevs = {prevtakexor};
			for (int i = prev; i < prev + 8; i++) prevs.pb(i);
			prevtakexor = add_or(prevs);
			int takexor = add_not(prevtakexor); // 1 if prev = 0
			// assign (pos & takexor & (cur & (1 << i))) to prev
			int nxt = -1;
			for (int i = 0; i < 8; i++) {
				int res = add_and({pos, takexor, (bool(cur & (1 << i)) ? ONE : ZERO)});
				if (nxt == -1) nxt = res;
			}
			prev = nxt;
			allprev.pb(nxt);
		}
		// only 1 has value, take or
		int ret = -1;
		for (int i = 0; i < 8; i++) {
			vector<int> v;
			for (int &x : allprev) v.pb(x + i);
			int res = add_or(v);
			if (ret == -1) ret = res;
		}
		return ret;
	};
	// stores position of max in range [st, en]
	function<int(int, int)> findmax = [&](int st, int en) -> int {
		int diff = en - st + 1;
		int prev = add_zero();
		for (int i = 1; i < 8; i++) add_zero();
		vector<int> allprev;
		int prevtakexor = add_zero();
		for (int cur = diff; cur >= 1; cur--) { // from max
			int pos = st + (cur - 1);
			// check if [prev, prev + 8) has value
			vector<int> prevs = {prevtakexor};
			for (int i = prev; i < prev + 8; i++) prevs.pb(i);
			prevtakexor = add_or(prevs);
			int takexor = add_not(prevtakexor); // 1 if prev = 0
			// assign (pos & takexor & (cur & (1 << i))) to prev
			int nxt = -1;
			for (int i = 0; i < 8; i++) {
				int res = add_and({pos, takexor, (bool(cur & (1 << i)) ? ONE : ZERO)});
				if (nxt == -1) nxt = res;
			}
			prev = nxt;
			allprev.pb(nxt);
		}
		// only 1 has value, take or
		int ret = -1;
		for (int i = 0; i < 8; i++) {
			vector<int> v;
			for (int &x : allprev) v.pb(x + i);
			int res = add_or(v);
			if (ret == -1) ret = res;
		}
		return ret;
	};

	// addition modulo 2^10 = 1024
	function<vector<int>(vector<int>, vector<int>)> add = [&](vector<int> lhs, vector<int> rhs) -> vector<int> {
		vector<int> res;
		int prev = add_zero(); // carrying
		res.pb(add_xor({lhs[0], rhs[0]}));
		for (int i = 1; i < 10; i++) {
			// handle carrying:
			// (prev, lhs[i - 1], rhs[i - 1]) >= 2
			// (AND = 1) or (XOR = 0 and OR = 1)
			// (AND) or (XOR xor OR) (no case where (XOR = 1 and OR = 0))
			vector<int> check = {prev, lhs[i - 1], rhs[i - 1]};
			int isthree = add_and(check);
			int istwo = add_xor({add_xor(check), add_or(check)});
			int fincarry = add_or({isthree, istwo});
			prev = fincarry;
			// calculate current bit
			res.pb(add_xor({prev, lhs[i], rhs[i]}));
		}
		return res;
	};

	int st = -1, en = -1;
	// find vertical
	for (int i = 0; i < n; i++) {
		vector<int> v;
		for (int j = 0; j < m; j++) v.pb(hash(i, j));
		int res = add_or(v);
		if (i == 0) st = res;
		if (i == n - 1) en = res;
	}
	int vmini = findmin(st, en);
	int vmaxi = findmax(st, en);
	// find horizontal
	for (int i = 0; i < m; i++) {
		vector<int> v;
		for (int j = 0; j < n; j++) v.pb(hash(j, i));
		int res = add_or(v);
		if (i == 0) st = res;
		if (i == m - 1) en = res;
	}
	int hmini = findmin(st, en);
	int hmaxi = findmax(st, en);

	// cerr << vmini << ' ' << vmaxi << ' ' << hmini << ' ' << hmaxi << endl;

	//   (vmax - vmin) + (hmax - hmin)
	// = (vmax + (1023 - vmin)) + (hmax + (1023 - hmin)) + 2 (mod 1024)
	// = (vmax + (vmin ^ 1023)) + (hmax + (hmin ^ 1023)) + 2 (mod 1024)

	vector<int> vmax(10), vmin(10), hmax(10), hmin(10);
	vector<int> two(10);
	for (int i = 0; i < 10; i++) {
		// take xor with mins
		vmax[i] = (i < 8 ? vmaxi + i : ZERO);
		vmin[i] = (i < 8 ? add_not(vmini + i) : ONE);
		hmax[i] = (i < 8 ? hmaxi + i : ZERO);
		hmin[i] = (i < 8 ? add_not(hmini + i) : ONE);
		two[i] = (i == 1 ? ONE : ZERO);
	}
	vector<int> res1 = add(vmax, vmin);
	vector<int> res2 = add(hmax, hmin);
	vector<int> dist = add(add(res1, res2), two);
	// compare dist and k
	vector<int> fin;
	for (int i = 0; i < 10; i++) {
		fin.pb(add_xor({dist[i], (bool(k & (1 << i)) ? ONE : ZERO)}));
	}
	add_not(add_or(fin));
}

• 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