Submission #946070

#	Time	Username	Problem	Language	Result	Execution time	Memory
946070		PenguinsAreCute	Vision Program (IOI19_vision)	C++17	0 / 100	10 ms	1748 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
// i dont think this is the intended solution...

// adds 2 bits. uses 2 instructions and 4 inputs.
vector<int> half_adder(int a, int b) {
	return {add_xor({a,b}),add_and({a,b})};
}
// adds 3 bits. uses 5 instructions and 12 inputs.
vector<int> full_adder(int a, int b, int c) {
	return {add_xor({a,b,c}), add_or({add_and({a,b}),add_and({b,c}),add_and({a,c})})};
}

// adds 2 9-bit integers. uses 42 instructions and 100 inputs.
vector<int> ninebit_add(vector<int> a, vector<int> b) {
	vector<int> ans(9);
	auto v = half_adder(a[0],b[0]);
	int carry = v[1]; ans[0] = v[0];
	for(int i=1;i<9;i++) {
		v = full_adder(a[i],b[i],carry);
		carry = v[1]; ans[i] = v[0];
	}
	return ans;
}
void construct_network(int H, int W, int K) {
	vector<int> x1(9), x2(9), y1(9), y2(9);
	int arr[max(H,W)], arr1[max(H,W)];
	for(int i=0;i<H;i++) {
		vector<int> v;
		for(int j=0;j<W;j++) v.push_back(i*W+j);
		arr[i] = add_or(v);
	}
	arr1[0] = arr[0];
	for(int i=1;i<H;i++) arr1[i] = add_or({arr1[i-1],arr[i]});
	for(int i=0;i<9;i++) {
		vector<int> v;
		for(int j=1;j<H;j++) if((-j)&(1<<i)) v.push_back(add_and({arr1[j],add_not(arr1[j-1])}));
		if(v.size()) x1[i] = add_or(v);
		else x1[i] = add_xor({0,0});
	}
	arr1[H-1] = arr[H-1];
	for(int i=H-1;i--;) arr1[i] = add_or({arr1[i+1],arr[i]});
	for(int i=0;i<9;i++) {
		vector<int> v;
		if((H-1)&(1<<i)) v.push_back(arr[H-1]);
		for(int j=0;j<H-1;j++) if(j&(1<<i)) v.push_back(add_and({arr[j],add_not(arr[j+1])}));
		if(v.size()) x2[i] = add_or(v);
		else x2[i] = add_xor({0,0});
	}

	for(int i=0;i<W;i++) {
		vector<int> v;
		for(int j=0;j<H;j++) v.push_back(j*W+i);
		arr[i] = add_or(v);
	}
	arr1[0] = arr[0];
	for(int i=1;i<W;i++) arr1[i] = add_or({arr1[i-1],arr[i]});
	for(int i=0;i<9;i++) {
		vector<int> v;
		for(int j=1;j<W;j++) if((-j)&(1<<i)) v.push_back(add_and({arr1[j],add_not(arr1[j-1])}));
		if(v.size()) y1[i] = add_or(v);
		else y2[i] = add_xor({0,0});
	}
	arr1[W-1] = arr[W-1];
	for(int i=W-1;i--;) arr1[i] = add_or({arr1[i+1],arr[i]});
	for(int i=0;i<9;i++) {
		vector<int> v;
		if((W-1)&(1<<i)) v.push_back(arr[W-1]);
		for(int j=0;j<W-1;j++) if(j&(1<<i)) v.push_back(add_and({arr[j],add_not(arr[j+1])}));
		if(v.size()) y2[i] = add_or(v);
		else y2[i] = add_xor({0,0});
	}
	vector<int> dist = ninebit_add(ninebit_add(x1,y1),ninebit_add(x2,y2));
	vector<int> v;
	for(int i=0;i<9;i++) v.push_back((K&(1<<i))?dist[i]:add_not(dist[i]));
	add_and(v);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 15
• Subtask 5: 0 / 12
• Subtask 6: 0 / 8
• Subtask 7: 0 / 14
• Subtask 8: 0 / 19