Submission #610852

#	Time	Username	Problem	Language	Result	Execution time	Memory
610852		fvogel499	Vision Program (IOI19_vision)	C++17	100 / 100	62 ms	7620 KiB

vision

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

#define vi vector<int>

using namespace std;

// #define size(x) (int)((x).size())

// vi b = {1, 0, 0, 0, 0, 1};

// int add_or(vi elems) {
// 	assert(!elems.empty());
// 	b.push_back(0);
// 	for (int i : elems) {
// 		b.back() |= b[i];
// 	}
// 	cout << "after OR operation: " << b.back() << endl;
// 	return size(b)-1;
// }

// int add_and(vi elems) {
// 	assert(!elems.empty());
// 	b.push_back(1);
// 	for (int i : elems) {
// 		b.back() &= b[i];
// 	}
// 	cout << "after AND operation: " << b.back() << endl;
// 	return size(b)-1;
// }

// int add_xor(vi elems) {
// 	assert(!elems.empty());
// 	b.push_back(0);
// 	for (int i : elems) {
// 		b.back() ^= b[i];
// 	}
// 	cout << "after XOR operation: " << b.back() << endl;
// 	return size(b)-1;
// }

// int add_not(int x) {
// 	b.push_back(!b[x]);
// 	cout << "after NOT operation: " << b.back() << endl;
// 	return size(b)-1;
// }

int check_k(int h, int w, int kConst) {
	vi on [2][h+w-1];
	for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
		int leftDiag = j - i + h - 1;
		assert(0 <= leftDiag && leftDiag < h+w-1);
		int rightDiag = i+j;
		assert(0 <= rightDiag && rightDiag < h+w-1);
		on[0][leftDiag].push_back(i*w+j);
		on[1][rightDiag].push_back(i*w+j);
	}
	int posOr [2][h+w-1];
	int posXor [2][h+w-1];
	int posNotXor [2][h+w-1];
	int posTwoContained [2][h+w-1];
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < h+w-1; j++) {
			posOr[i][j] = add_or(on[i][j]);
			posXor[i][j] = add_xor(on[i][j]);
			posNotXor[i][j] = add_not(posXor[i][j]);
			posTwoContained[i][j] = add_and({posOr[i][j], posNotXor[i][j]});
		}
	}
	int finalAnswer [2];
	for (int i = 0; i < 2; i++) {
		vi toOr;
		for (int j = 0; j < h+w-1; j++) {
			toOr.push_back(posTwoContained[i][j]);
		}
		for (int j = 0; j < h+w-1 -1; j++) {
			vi consecutive;
			for (int k = j+1; k < min(h+w-1, j+1+kConst); k++) {
				consecutive.push_back(posOr[i][k]);
			}
			int orAllConsecutive = add_or(consecutive);
			toOr.push_back(add_and({posOr[i][j], orAllConsecutive}));
		}
		finalAnswer[i] = add_or(toOr);
	}
	int ansAt = add_and({finalAnswer[0], finalAnswer[1]});
	return ansAt;
}

void construct_network(int h, int w, int k) {
	int kAt = check_k(h, w, k);
	if (k >= 2) {
		int smKAt = check_k(h, w, k - 1);
		int notSmKAt = add_not(smKAt);
		add_and({kAt, notSmKAt});
	}
}

• 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