Submission #418010

#	Time	Username	Problem	Language	Result	Execution time	Memory
418010		SuhaibSawalha1	Vision Program (IOI19_vision)	C++17	66 / 100	953 ms	9724 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
 
void construct_network(int n, int m, int k) {
	vector<int> OR;
	vector<int> row(n), col(m);
	int xor_for_rows, xor_for_cols;
	auto init = [&] () {
		for (int i = 0; i < n; ++i) {
			vector<int> p;
			for (int j = 0; j < m; ++j) {
				p.push_back(i * m + j);
			}
			row[i] = add_or(p);
		}
		for (int j = 0; j < m; ++j) {
			vector<int> p;
			for (int i = 0; i < n; ++i) {
				p.push_back(i * m + j);
			}
			col[j] = add_or(p);
		}
		xor_for_rows = add_xor(row), xor_for_cols = add_xor(col);
	};
	if (k == 1) {
		init();
		for (int i = 1; i < n; ++i) {
			OR.push_back(add_and({row[i - 1], row[i], xor_for_cols}));
		}
		for (int i = 1; i < m; ++i) {
			OR.push_back(add_and({col[i - 1], col[i], xor_for_rows}));
		}
	}
	else if (max(n, m) <= 100) {
		init();
		vector<vector<int>> dist(n);
		vector<int> dist_or(n);
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				dist[j - i].push_back(add_and({row[i], row[j]}));
			}
		}
		for (int i = 1; i < n; ++i) {
			dist_or[i] = add_or(dist[i]);
		}
		for (int i = 0; i < m; ++i) {
			for (int j = i + 1; j < m; ++j) {
				if (j - i == k) {
					OR.push_back(add_and({col[i], col[j], xor_for_rows}));
				}
				else if (j - i < k && k - j + i < n) {
					OR.push_back(add_and({col[i], col[j], dist_or[k - j + i]}));
				}
			}
		}
		if (k < n) {
			OR.push_back(add_and({dist_or[k], xor_for_cols}));
		}
	}
	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 (abs(i - h) + abs(j - w) == k && q > 1) {
							ask.push_back(h * m + w);
						}
					}
				}
				if (ask.size()) {
					q -= 2;
					OR.push_back(add_and({i * m + j, add_xor(ask)}));
				}
			}
		}
	}
	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