Submission #480533

#	Time	Username	Problem	Language	Result	Execution time	Memory
480533		couplefire	Vision Program (IOI19_vision)	C++17	100 / 100	16 ms	2288 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
 
using namespace std;
 
int AtLeastK(const vector<int>& xors, int k) {
	int aux = add_not(0);
	int zero = add_and({0, aux});
	int n = static_cast<int>(xors.size());
	vector<int> inputs;
	for (int i = 0; i < n - k + 1; ++i) {
		int aux_and = add_and({xors[i], xors[i + k - 1]});
		inputs.push_back(aux_and);
	}
 
	return inputs.empty() ? zero : add_or(inputs);
}
 
pair<int, int> GetVars(const vector<int>& xors, int k) {
	int x = AtLeastK(xors, k);
	int y = AtLeastK(xors, k + 1);
	int first = add_not(x);
	int z = add_not(y);
	int second = add_and({x, z});
	return {first, second};
}
 
void construct_network(int H, int W, int K) {
	map<int, vector<pair<int, int>>> diag[2];
 
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			diag[0][i + j].emplace_back(i, j);
			diag[1][i - j].emplace_back(i, j);
		}
	}
 
	vector<int> xors[2];
	for (int d = 0; d < 2; ++d) {
		for (const auto& item: diag[d]) {
			vector<int> inputs;
			if (!xors[d].empty()) inputs.push_back(xors[d].back());
			for (const auto& point: item.second) {
				inputs.push_back(point.first * W + point.second);
			}
 
			xors[d].push_back(add_xor(inputs));
		}
	}
 
	auto first = GetVars(xors[0], K);
	auto second = GetVars(xors[1], K);
 
	int x = add_and({first.first, second.second});
	int y = add_and({second.first, first.second});
	int z = add_and({first.second, second.second});
 
	add_or({x, y, z});
}

• 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