Submission #589719

#	Time	Username	Problem	Language	Result	Execution time	Memory
589719		Zanite	Vision Program (IOI19_vision)	C++17	100 / 100	65 ms	5856 KiB

vision

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

int H, W, K;
map<int, vector<int>> d1, d2;

int XL[2], XR[2], OL[2], OR[2];

inline int cell(int i, int j) {return i*W + j;}

void process(map<int, vector<int>> &M, int T) {
	int cur = -1;
	for (auto &[i, v] : M) {
		int nxt = add_xor(v);
		if (cur == -1) {XL[T] = nxt;}
		cur = nxt;
	}
	XR[T] = cur;

	cur = -1;
	for (auto &[i, v] : M) {
		int nxt = add_or(v);
		if (cur == -1) {OL[T] = nxt;}
		cur = nxt;
	}
	OR[T] = cur;
}

int solve(int D) {
	vector<int> G[2];

	for (int i = 0; i <= 1; i++) {
		for (int st = XL[i], ost = OL[i]; st <= XR[i]-D+1; st++, ost++) {
			vector<int> X(D), O(D);
			iota(X.begin(), X.end(), st);
			iota(O.begin(), O.end(), ost);

			int xres, ores;
			xres = add_xor(X);
			xres = add_not(xres);
			ores = add_or(O);
			G[i].push_back(add_and({xres, ores}));
		}
	}

	int r[2];
	for (int i = 0; i <= 1; i++) {r[i] = add_or(G[i]);}
	return add_and({r[0], r[1]});
}

void construct_network(int H, int W, int K) {
	::H = H, ::W = W, ::K = K;
	d1.clear(), d2.clear();

	if (K == H + W - 2) {
		int UL = add_and({cell(0, 0), cell(H-1, W-1)});
		int UR = add_and({cell(0, W-1), cell(H-1, 0)});
		add_or({UL, UR});

		return;
	}

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			d1[i+j].push_back(cell(i, j));
			d2[i-j].push_back(cell(i, j));
		}
	}

	process(d1, 0);
	process(d2, 1);

	int x1 = solve(K+1);
	int x2 = solve(K);
	x2 = add_not(x2);

	add_and({x1, x2});
}

#ifdef Zanite

static const int MAX_INSTRUCTIONS = 10000;
static const int MAX_INPUTS = 1000000;

static const int _AND = 0;
static const int _OR = 1;
static const int _XOR = 2;
static const int _NOT = 3;

static inline bool increasing(int a, int b, int c) {
	return a <= b && b <= c;
}

[[noreturn]] static inline void error(string message) {
	printf("%s\n", message.c_str());
	exit(0);
}

class InstructionNetwork {

	struct Instruction {
		int type;
		vector<int> input_indexes;

		inline Instruction(int _type, const vector<int>& _input_indexes):
				type(_type), input_indexes(_input_indexes) {
		}

		inline int apply(int a, int b) const {
			switch (type) {
				case _AND:
					return a & b;
				case _OR:
					return a | b;
				case _XOR:
					return a ^ b;
				default:
					return 0;
			}
		}

		inline int compute(const vector<int>& memory_cells) const {
			int r = memory_cells[input_indexes[0]];
			if (type == _NOT)
				return 1 - r;
			for (int j = 1; j < (int)input_indexes.size(); j++)
				r = apply(r, memory_cells[input_indexes[j]]);
			return r;
		}
	};

	int input_size;
	int total_inputs;
	vector<Instruction> instructions;

public:

	inline void init(int _input_size) {
		this->input_size = _input_size;
		this->total_inputs = 0;
		this->instructions.clear();
	}

	inline int add_instruction(int type, const vector<int>& input_indexes) {
		if (input_indexes.size() == 0)
			error("Instruction with no inputs");

		if (instructions.size() + 1 > MAX_INSTRUCTIONS)
			error("Too many instructions");

		if (total_inputs + input_indexes.size() > MAX_INPUTS)
			error("Too many inputs");

		instructions.emplace_back(type, input_indexes);
		total_inputs += input_indexes.size();
		int new_index = input_size + (int)instructions.size() - 1;

		for (int input_index : input_indexes)
			if (!increasing(0, input_index, new_index-1))
				error("Invalid index");

		return new_index;
	}

	inline int compute(vector<int> &memory_cells) const {
		for (auto &instruction : instructions)
			memory_cells.push_back(instruction.compute(memory_cells));
		return memory_cells.back();
	}
};


static InstructionNetwork instructionNetwork;

int main() {
	int H, W, K;
	assert(3 == scanf("%d%d%d", &H, &W, &K));

	FILE *log_file = fopen("log.txt","w");

	instructionNetwork.init(H * W);
	construct_network(H, W, K);

	while (true) {
		int rowA, colA, rowB, colB;
		assert(1 == scanf("%d", &rowA));
		if (rowA == -1)
			break;
		assert(3 == scanf("%d%d%d", &colA, &rowB, &colB));

		if ((!increasing(0, rowA, H-1)) ||
			(!increasing(0, colA, W-1)) ||
			(!increasing(0, rowB, H-1)) ||
			(!increasing(0, colB, W-1)) ||
			(rowA == rowB && colA == colB)) {
			printf("-1\n");
			fprintf(log_file, "-1\n");
			fflush(stdout);
			fflush(log_file);
			continue;
		}

		vector<int> memory_cells;
		for (int row = 0; row < H; row++)
			for (int col = 0; col < W; col++) {
				bool active = (row == rowA && col == colA) || (row == rowB && col == colB);
				memory_cells.push_back(active ? 1 : 0);
			}
		int computation_result = instructionNetwork.compute(memory_cells);

		printf("%d\n", computation_result);
		fflush(stdout);

		for(int i = 0; i < (int)memory_cells.size(); i++)
			fprintf(log_file, (i ? " %d" : "%d"), memory_cells[i]);
		fprintf(log_file, "\n");
		fflush(log_file);
	}
	fclose(stdin);
}

int add_and(vector<int> Ns) {
	return instructionNetwork.add_instruction(_AND, Ns);
}

int add_or(vector<int> Ns) {
	return instructionNetwork.add_instruction(_OR, Ns);
}

int add_xor(vector<int> Ns) {
	return instructionNetwork.add_instruction(_XOR, Ns);
}

int add_not(int N) {
	vector<int> Ns = {N};
	return instructionNetwork.add_instruction(_NOT, Ns);
}

#endif

• 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