oj.uz

Submission #241495

# Submission time Handle Problem Language Result Execution time Memory
241495 2020-06-24T09:30:59 Z mosesmayer Vision Program (IOI19_vision) C++17
0 / 100
 1000 ms 916260 KB 
#include "vision.h"
#include <tuple>

using namespace std;

int H, W;
int coord(int i, int j) {
	return i * W + j;
};

vector<int> get_cells(int D, bool dir) {
	// dir is 1 if left diagonal (sum), 0 if right diagonal.
	vector<int> res;
	int start, stop, diff;
	if (dir) {
		start = D < W ? D : (D - W + 1) * W + (W - 1);
		stop = D < H ? D * W : (H - 1) * W + (D - H + 1);
		diff = W - 1;
	} else {
		start = D < W ? W - 1 - D : (D - W + 1) * W;
		stop = D < H ? (D + 1) * W - 1 : H * W - 1 - (D - H + 1);
		diff = W + 1;
	}
	for (; start <= stop; start += diff)
		res.emplace_back(start);
	return res;
}

void construct_diagonals(bool dir, vector<int>& orv, vector<int>& xorv) {
	for (int i = 0; i <= H + W - 2; i++) {
		vector<int> cur = get_cells(i, dir);
		// printf("add %s squares: ", dir ? "left" : "right");
		// for (int i : cur) {
		// 	printf("%d ", i);
		// }
		// puts("");
		orv.emplace_back(add_or(cur));
		xorv.emplace_back(add_xor(cur));
	}
}

int test(const vector<int>& orv, const vector<int>& xorv, int D) {
	// tests if there are D consecutive diagonals which has 2 black.
	vector<int> cur_or(D), cur_xor(D), res;
	for (int i = 0, t = orv.size(); i < t; i++) {
		cur_or[i % D] = orv[i];
		cur_xor[i % D] = xorv[i];
		if (i >= D - 1)
			res.emplace_back(add_and({add_or(cur_or),
					         add_not(add_xor(cur_xor)) // odd iff exactly 1.
			}));
	}
	return add_or(res);
}

void construct_network(int H, int W, int K) {
	tie(::H, ::W) = {H, W};
//	std::vector<int> Ns;
//	Ns = {0, 1};
//	int a = add_and(Ns);
//	Ns = {0, a};
//	int b = add_or(Ns);
//	Ns = {0, 1, b};
//	int c = add_xor(Ns);
//	add_not(c);

	vector<int> left_diags_or, right_diags_or;
	vector<int> left_diags_xor, right_diags_xor;

	// Base diagonal processing
	construct_diagonals(1, left_diags_or, left_diags_xor);
	construct_diagonals(0, right_diags_or, right_diags_xor);

	// or -> 1 if has black pixel in diag, 0 otherwise
	// xor -> if 0 where or is 1, then 2 black in diag. if 1 then 1 black.
	// if consecutive diagonals, if xor of xor's = 1 then exactly 1 black
	// if or of or's = 1 then >= 1 black.
	// if xor of xor's = 0 then even num of blacks.
	// want or of or's = 1 and xor of xor's = 0.

	int k1val = add_and({test(left_diags_or, left_diags_xor, K + 1),
						test(right_diags_or,right_diags_xor, K + 1)});
	int kval = add_and({test(left_diags_or, left_diags_xor, K),
						test(right_diags_or,right_diags_xor, K)});
	// want k1val true and kval false.
	add_and({k1val, add_xor({kval, k1val})});
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Execution timed out 1147 ms 876992 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Execution timed out 1147 ms 876992 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Execution timed out 1147 ms 876992 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Execution timed out 1147 ms 876992 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 620 KB Output is correct
2 Correct 15 ms 1152 KB Output is correct
3 Correct 13 ms 1152 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Execution timed out 1155 ms 878324 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 10 ms 768 KB Output is correct
5 Correct 10 ms 768 KB Output is correct
6 Correct 9 ms 768 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 9 ms 768 KB Output is correct
9 Correct 13 ms 1152 KB Output is correct
10 Correct 14 ms 1280 KB Output is correct
11 Correct 13 ms 1024 KB Output is correct
12 Correct 8 ms 512 KB Output is correct
13 Correct 7 ms 640 KB Output is correct
14 Correct 12 ms 1152 KB Output is correct
15 Correct 12 ms 1024 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Execution timed out 1158 ms 916260 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2420 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 9 ms 768 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Execution timed out 1155 ms 898888 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Execution timed out 1147 ms 876992 KB Time limit exceeded
4 Halted 0 ms 0 KB -