Submission #1048731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048731		aykhn	Vision Program (IOI19_vision)	C++17	100 / 100	28 ms	5404 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>

using namespace std;

const int LOG = 8;

void construct_network(int H, int W, int K) 
{
	vector<int> br(LOG, -1), bc(LOG, -1);
	vector<int> inr(H), inc(W);
	vector<int> sr, sc;
	int samr, samc;
	for (int i = 0; i < H; i++)
	{
		vector<int> v;
		for (int j = 0; j < W; j++) v.push_back(i * W + j);
		inr[i] = add_or(v);
		sr.push_back(add_xor(v));
	}
	for (int j = 0; j < W; j++)
	{
		vector<int> v;
		for (int i = 0; i < H; i++) v.push_back(i * W + j);
		inc[j] = add_or(v); 
		sc.push_back(add_xor(v));
	}
	samr = add_not(add_or(sr));
	samc = add_not(add_or(sc));
	for (int i = 0; i < LOG; i++)
	{
		int d = (1 << i);
		if (d > H - 1) continue;
		vector<int> all;
		for (int j = 0; j < H; j++)
		{
			vector<int> v;
			for (int k = 0; k < H; k++) 
			{
				if (abs((k - j)) >> i & 1) v.push_back(inr[k]);
			}
			if (v.empty()) continue;
			all.push_back(add_and({inr[j], add_or(v)}));
		}
		br[i] = add_or(all);
	}
	for (int i = 0; i < LOG; i++)
	{
		int d = (1 << i);
		if (d > W - 1) continue;
		vector<int> all;
		for (int j = 0; j < W; j++)
		{
			vector<int> v;
			for (int k = 0; k < W; k++) 
			{
				if (abs((k - j)) >> i & 1) v.push_back(inc[k]);
			}
			if (v.empty()) continue;
			all.push_back(add_and({inc[j], add_or(v)}));
		}
		bc[i] = add_or(all);
	}
	vector<int> res;
	for (int dr = 0; dr <= min(H - 1, K); dr++)
	{
		int dc = K - dr;
		if (dc >= W) continue;
		vector<int> onr, offr, onc, offc;
		for (int b = 0; b < LOG; b++)
		{
			if ((dr >> b & 1)) onr.push_back(br[b]);
			else if (br[b] != -1) offr.push_back(br[b]);
			if ((dc >> b & 1)) onc.push_back(bc[b]);
			else if (bc[b] != -1) offc.push_back(bc[b]);
		}
		if (!dr)
		{
			assert(!onc.empty());
			int canc;
			if (!offc.empty()) canc = add_and({add_and(onc), add_not(add_or(offc))});
			else canc = add_and(onc);
			res.push_back(add_and({samr, canc}));
		}
		else if (!dc)
		{
			int canr;
			if (!offr.empty()) canr = add_and({add_and(onr), add_not(add_or(offr))});
			else canr = add_and(onr);
			res.push_back(add_and({samc, canr}));
		}
		else
		{
			int canr;
			if (!offr.empty()) canr = add_and({add_and(onr), add_not(add_or(offr))});
			else canr = add_and(onr);
			int canc;
			if (!offc.empty()) canc = add_and({add_and(onc), add_not(add_or(offc))});
			else canc = add_and(onc);
			res.push_back(add_and({canr, canc}));
		}
	}
	add_or(res);
}

• 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