Submission #596874

#	Time	Username	Problem	Language	Result	Execution time	Memory
596874		Temmie	Vision Program (IOI19_vision)	C++17	100 / 100	66 ms	6648 KiB

vision

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

struct Diag {
	std::vector <std::pair <int, int>> a;
	Diag(const std::set <std::pair <int, int>>& st) {
		for (const auto& p : st) {
			a.emplace_back(p);
		}
	}
	int ind_or;
	int ind_xor;
	int ind_not_xor;
	int ind_has_two;
};

constexpr bool ok(int i, int j, int n, int m) {
	return i >= 0 && j >= 0 && i < n && j < m;
}

std::vector <int> conv(int m, const std::vector <std::pair <int, int>>& a) {
	std::vector <int> res(a.size());
	for (int i = 0; i < (int) a.size(); i++) {
		res[i] = a[i].first * m + a[i].second;
	}
	return res;
}

void construct_network(int n, int m, int k) {
	std::vector <Diag> up, down;
	{
		std::set <std::pair <int, int>> st;
		st.insert({ 0, 0 });
		while (st.size()) {
			down.push_back(Diag(st));
			std::set <std::pair <int, int>> stt;
			for (auto p : st) {
				if (ok(p.first + 1, p.second, n, m)) stt.insert({ p.first + 1, p.second });
				if (ok(p.first, p.second + 1, n, m)) stt.insert({ p.first, p.second + 1 });
			}
			st = stt;
		}
	}
	{
		std::set <std::pair <int, int>> st;
		st.insert({ n - 1, 0 });
		while (st.size()) {
			up.push_back(Diag(st));
			std::set <std::pair <int, int>> stt;
			for (auto p : st) {
				if (ok(p.first - 1, p.second, n, m)) stt.insert({ p.first - 1, p.second });
				if (ok(p.first, p.second + 1, n, m)) stt.insert({ p.first, p.second + 1 });
			}
			st = stt;
		}
	}
	for (Diag& d : down) {
		d.ind_or = add_or(conv(m, d.a));
		d.ind_xor = add_xor(conv(m, d.a));
		d.ind_not_xor = add_not(d.ind_xor);
		d.ind_has_two = add_and({ d.ind_or, d.ind_not_xor });
	}
	for (Diag& d : up) {
		d.ind_or = add_or(conv(m, d.a));
		d.ind_xor = add_xor(conv(m, d.a));
		d.ind_not_xor = add_not(d.ind_xor);
		d.ind_has_two = add_and({ d.ind_or, d.ind_not_xor });
	}
	//{ not xor { or } } and { or }
	//or
	//or { d.ind_has_two }
	auto go = [] (const std::vector <Diag>& diag, int kk) -> int {
		std::vector <int> inds;
		std::vector <Diag> cur;
		for (const Diag& d : diag) {
			cur.push_back(d);
			if ((int) cur.size() > kk) {
				cur.erase(cur.begin());
			}
			assert((int) cur.size() <= kk);
			if ((int) cur.size() == kk) {
				std::vector <int> idx;
				for (const Diag& dd : cur) {
					idx.push_back(dd.ind_or);
				}
				int ind_or = add_or(idx);
				int ind_xor = add_xor(idx);
				//int ind_not_xor = add_not(ind_xor);
				//int ind_and = add_and({ ind_not_xor, ind_or });
				int ind_and = add_xor({ ind_or, ind_xor });
				//idx.clear();
				//for (const Diag& dd : cur) {
					//idx.push_back(dd.ind_has_two);
				//}
				//int ind_h2_or = add_or(idx);
				//inds.push_back(add_or({ ind_and, ind_h2_or }));
				inds.push_back(ind_and);
			}
		}
		std::vector <int> all_ind_h2_or;
		for (const Diag& d : diag) {
			all_ind_h2_or.push_back(d.ind_has_two);
		}
		int ind_h2_or = add_or(all_ind_h2_or);
		inds.push_back(ind_h2_or);
		return add_or(inds);
	};
	int ind_kp1_up = go(up, k + 1);
	int ind_kp1_down = go(down, k + 1);
	int ind_kp0_up = go(up, k);
	int ind_kp0_down = go(down, k);
	
	int ind_kp1_both = add_and({ ind_kp1_up, ind_kp1_down });
	int ind_kp0_both = add_and({ ind_kp0_up, ind_kp0_down });
	
	int ind_kp0_not = add_not(ind_kp0_both);
	
	add_and({ ind_kp1_both, ind_kp0_not });
}

• 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