Submission #749767

#	Time	Username	Problem	Language	Result	Execution time	Memory
749767		Alan	Vision Program (IOI19_vision)	C++17	100 / 100	11 ms	1488 KiB

vision

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

int id, id0, id1;
vector<vector<int>> bruh;

vector<int> extract(vector<int> bits, int guard_id, int x) {
	vector<vector<int>> t (8);
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < 8; j++) if (i & (1<<j)) t[j].push_back(add_and({guard_id, bits[i]}));
		guard_id = add_xor({guard_id, bits[i]});
	}
	vector<int> res (8, id0);
	for (int i = 0; i < 8; i++) if (!t[i].empty()) res[i] = add_or(t[i]);
	return res;
}

vector<int> add (vector<int> a, vector<int> b) {
	int sz = a.size();
	vector<int> res, carry {id0};
	for (int i = 0; i < sz; i++) {
		int xor_id = add_xor({a[i], b[i]});
		res.push_back(add_xor({xor_id, carry[i]}));
		carry.push_back(add_or({add_and({a[i], b[i]}), add_and({xor_id, carry[i]})}));
	}
	res.push_back(carry.back());
	return res;
}

vector<int> neg (vector<int> bits) {
	int sz = bits.size();
	vector<int> t, one {id1};
	for (int i = 0; i < sz; i++) t.push_back(add_not(bits[i]));
	for (int i = 1; i < sz; i++) one.push_back(id0);
	vector<int> res = add(t, one);
	res.pop_back();
	return res;
}

vector<int> proc(vector<int> ids, int x) {
	int guard_id = id1;
	vector<int> pos_id1 = extract(ids, guard_id, x);
	guard_id = id0;
	vector<int> pos_id2 = extract(ids, guard_id, x);
	pos_id1 = neg(pos_id1);
	vector<int> res = add(pos_id1, pos_id2);
	res.pop_back();
	return res;
}

void construct_network(int H, int W, int K) {
	id = H*W;
	vector<int> rid, cid;
	for (int i = 0; i < H; i++) {
		vector<int> v;
		for (int j = i*W; j < (i+1)*W; j++) v.push_back(j);
		rid.push_back(add_xor(v));
	}
	for (int i = 0; i < W; i++) {
		vector<int> v;
		for (int j = i; j < H*W; j += W) v.push_back(j);
		cid.push_back(add_xor(v));
	}
	id0 = add_and({0, add_not(0)});
	id1 = add_not(id0);
	vector<int> diffr = proc(rid, H), diffc = proc(cid, W);
	vector<int> diff = add(diffr, diffc);
	K--;
	vector<int> kid;
	for (int i = 0; i < 9; i++) kid.push_back((K & (1<<i)) ? id0 : id1);
	vector<int> res = add(diff, kid);
	res.pop_back();
	int ans_inv = add_or(res);
	add_not(ans_inv);
}

• 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