Submission #439196

#	Time	Username	Problem	Language	Result	Execution time	Memory
439196		dutch	Vision Program (IOI19_vision)	C++17	100 / 100	18 ms	1440 KiB

vision

#include <bits/stdc++.h>
using namespace std;
#include "vision.h"
#define G(i, j) (rotated ? j*h + i : i*w + j)
#define V(i, j) vector<int> {i, j}

const int N = 200, BIT = 8;
int a[N], b[2][N], p, pTrue, pFalse;
bool rotated = 0;

vector<int> sum(vector<int> &x, vector<int> &y){
	vector<int> res(BIT);
	int extra = pFalse;
	for(int c=0; c<BIT; ++c){
		add_xor(vector<int> {x[c], y[c], extra}); res[c] = p++;

		add_and(V(x[c], extra)); int a1 = p++;
		add_and(V(y[c], extra)); int a2 = p++;
		add_and(V(x[c], y[c])); int a3 = p++;
		add_or(vector<int> {a1, a2, a3}); extra = p++;
	}

	return res;
}

void construct_network(int h, int w, int k){
	if((p = h*w) < 3) return void(add_and(V(0, 1)));
	add_and(vector<int> {0, 1, 2}); pFalse = p++;
	add_not(pFalse); pTrue = p++;
	vector<int> one(BIT, pFalse); one[0] = pTrue;

	vector<int> res[2];

	for(int _=0; _<2; ++_){
		rotated = !rotated;
		swap(h, w);
		for(int i=0; i<h; ++i){
			vector<int> q(w);
			for(int j=0; j<w; ++j) q[j] = G(i, j);
			add_or(q); a[i] = p++;
		}

		b[0][0] = b[1][h-1] = pTrue;

		for(int i=1; i<h; ++i)
			add_xor(V(b[0][i-1], a[i-1])), b[0][i] = p++;
		for(int i=h-2; i>=0; --i)
			add_xor(V(b[1][i+1], a[i+1])), b[1][i] = p++;

		vector<vector<int>> num(2, vector<int> (BIT));
		for(int c=0; c<BIT; ++c){
			vector<int> curr[2];
			for(int i=0; i<h; ++i) if(i & (1<<c))
				for(int j=0; j<2; ++j)
					add_and(V(a[i], b[j][i])), curr[j].push_back(p++);
			for(int j=0; j<2; ++j){
				if(curr[j].empty()) num[j][c] = pFalse;
				else add_or(curr[j]), num[j][c] = p++;
			}
			add_not(num[0][c]); num[0][c] = p++;
		}
		res[_] = sum(num[0], num[1]);
		// res[_] = sum(res[_], one);
	}
	vector<int> ans = sum(res[0], res[1]);
	vector<int> two(BIT, pFalse); two[1] = pTrue;
	ans = sum(ans, two);
	vector<int> bits[2];
	for(int c=0; c<BIT; ++c)
		bits[bool((1<<c) & k)].push_back(ans[c]);
	add_and(bits[1]); int on = p++;
	add_or(bits[0]);
	add_not(p++);
	add_and(V(on, p++));
}

• 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