Submission #390178

#	Time	Username	Problem	Language	Result	Execution time	Memory
390178		SuhaibSawalha1	Vision Program (IOI19_vision)	C++17	66 / 100	897 ms	7152 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;

int dist (array<int, 2> a, array<int, 2> b) {
	return abs(a[0] - b[0]) + abs(a[1] - b[1]);
}

void construct_network(int n, int m, int k) {
	auto val = [&] (int i, int j) {
		return i * m + j;
	};
	vector<int> OR;
	int cur = n * m - 1;
	if (k == 1) {
		int row[n], col[m];
		int xor_for_rows, xor_for_cols;
		vector<int> ask_r, ask_c;
		for (int i = 0; i < n; ++i) {
			vector<int> p;
			for (int j = 0; j < m; ++j) {
				p.push_back(val(i, j));
			}
			add_or(p);
			row[i] = ++cur;
			ask_r.push_back(cur);
		}
		for (int j = 0; j < m; ++j) {
			vector<int> p;
			for (int i = 0; i < n; ++i) {
				p.push_back(val(i, j));
			}
			add_or(p);
			col[j] = ++cur;
			ask_c.push_back(cur);
		}
		add_xor(ask_r);
		xor_for_rows = ++cur;
		add_xor(ask_c);
		xor_for_cols = ++cur;
		for (int i = 1; i < n; ++i) {
			add_and({row[i - 1], row[i], xor_for_cols});
			OR.push_back(++cur);
		}
		for (int i = 1; i < m; ++i) {
			add_and({col[i - 1], col[i], xor_for_rows});
			OR.push_back(++cur);
		}
	}
	else {
		int q = 1e4 - 1;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				vector<int> ask;
				for (int h = i; h < n; ++h) {
					for (int w = (i == h ? j : 0); w < m; ++w) {
						if (dist({i, j}, {h, w}) == k && q) {
							ask.push_back(val(h, w));
						}
					}
				}
				if (ask.size() && q > 2) {
					ask.push_back(val(i, j));
					add_xor(ask), ++cur;
					add_not(cur), ++cur;
					add_and({val(i, j), cur}); ++cur;
					q -= 3;
					OR.push_back(cur);
				}
			}
		}
	}
	add_or(OR);
}

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