Submission #417163

#	Time	Username	Problem	Language	Result	Execution time	Memory
417163		Mlxa	Vision Program (IOI19_vision)	C++14	100 / 100	33 ms	1524 KiB

vision

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "vision.h"

int add_or(int x, int y) {
	return add_or(vector<int>({x, y}));
}
int add_and(int x, int y) {
	return add_and(vector<int>({x, y}));
}

#define N 210

int su[2 * N], di[2 * N];
int ls[2 * N], rs[2 * N], ld[2 * N], rd[2 * N];
// su[q]: i + j = q, q in [0; h + w - 2]
// di[q]: i + w - 1 - j = q, q in [0; h + w - 2]
#undef N 

void construct_network(int h, int w, int k) {
	// int ff = h * w;
	for (int q = 0; q <= h + w - 2; ++q) {
		vector<int> ss, dd;
		for (int i = 0; i < h; ++i) {
			for (int j = 0; j < w; ++j) {
				if (i + j == q) {
					ss.push_back(i * w + j);
				}
				if (i + w - 1 - j == q) {
					dd.push_back(i * w + j);
				}
			}
		}
		assert(ss.size());
		assert(dd.size());
		su[q] = add_or(ss);
		di[q] = add_or(dd);
	}
	ls[0] = su[0], ld[0] = di[0], rs[h + w - 2] = su[h + w - 2], rd[h + w - 2] = di[h + w - 2];
	for (int i = 1; i <= h + w - 2; ++i) {
		ls[i] = add_or(su[i], ls[i - 1]);
		ld[i] = add_or(di[i], ld[i - 1]);
	}
	for (int i = h + w - 3; i >= 0; --i) {
		rs[i] = add_or(su[i], rs[i + 1]);
		rd[i] = add_or(di[i], rd[i + 1]);
	}
	int one = add_or(0, add_not(0));
	int zero = add_not(one);

	vector<int> eq = {zero}, gr = {zero};
	for (int i = 0; i + k <= h + w - 2; ++i) {
		eq.push_back(add_and(su[i], su[i + k]));
		eq.push_back(add_and(di[i], di[i + k]));
	}
	for (int i = 0; i + k < h + w - 2; ++i) {
		gr.push_back(add_and(su[i], rs[i + k + 1]));
		gr.push_back(add_and(di[i], rd[i + k + 1]));
	}
	int eq_flag = add_or(eq);
	int gr_flag = add_not(add_or(gr));
	add_and(eq_flag, gr_flag);
}

#ifdef LC
#include "grader.cpp"
#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