oj.uz

Submission #1079694

# Submission time Handle Problem Language Result Execution time Memory
1079694 2024-08-28T21:29:35 Z BestCrazyNoob Vision Program (IOI19_vision) C++17
0 / 100
 15 ms 2004 KB 
#include "vision.h"
#include <vector>
#include <array>

using namespace std;

constexpr int BITS = 9;					// ############## TODO ###############à //
using BITINT = array<int, BITS>;

BITINT createInt(int x, int zero, int one) {
	BITINT res;
	for (int h = 0; h < BITS; h++) {
		res[h] = (x & (1 << h)) ? add_or({one}) : add_or({zero});
	}
	return res;
}

BITINT doCreateInt(int x, int zero) {
	BITINT res;
	for (int h = 0; h < BITS; h++) {
		res[h] = (x & (1 << h)) ? add_not(zero) : add_or({zero});
	}
	return res;
}

BITINT orInt(vector<BITINT> v) {
	BITINT res;
	for (int h = 0; h < BITS; h++) {
		vector<int> vh;
		for (BITINT b: v) vh.push_back(b[h]);
		res[h] = add_or(vh);
	}
	return res;
}

BITINT addInt(BITINT a, BITINT b) {
	BITINT res;
	res[0] = add_xor({a[0], b[0]});
	int carry = add_and({a[0], b[0]});
	for (int h = 1; h < BITS; h++) {
		res[h] = add_xor({a[h], b[h], carry});
		carry = add_or({
			add_and({a[h], b[h]}),
			add_and({carry, add_xor({a[h], b[h]})}
		)});
	}
	return res;
}

int equal(BITINT a, BITINT b) {
	vector<int> _xor;
	for (int h = 0; h < BITS; h++) {
		_xor.push_back(add_xor({a[h], b[h]}));
	}
	return add_not(add_or(_xor));
}

void construct_network(int H, int W, int K) {
	auto get = [&](int i, int j) {
		return W*i + j;
	};

	int zero = add_and({0, 1, 2});

	vector<int> rowOr, ySweep(H), rySweep(H);
	vector<BITINT> ys1(H), ys2(H);
	for (int i = 0; i < H; i++) {
		vector<int> Y;
		for (int j = 0; j < W; j++) Y.push_back(get(i, j));
		rowOr.push_back(add_or(Y));
	}

	ySweep[0] = add_or({rowOr[0]});
	ys1[0] = createInt(0, zero, ySweep[0]);
	for (int i = 1; i < H; i++) {
		ySweep[i] = add_or({rowOr[i], ySweep[i-1]});
		ys1[i] = createInt(i, zero, add_xor({ySweep[i-1], ySweep[i]}));
	}

	rySweep[H-1] = add_or({rowOr[H-1]});
	ys2[H-1] = createInt(H-1, zero, rySweep[H-1]);
	for (int i = H-2; i >= 0; i--) {
		rySweep[i] = add_or({rowOr[i], rySweep[i+1]});
		ys2[i] = createInt(i, zero, add_xor({rySweep[i+1], rySweep[i]}));
	}

	vector<int> colOr, xSweep(W), rxSweep(W);
	vector<BITINT> xs1(W), xs2(W);
	for (int j = 0; j < W; j++) {
		vector<int> Y;
		for (int i = 0; i < H; i++) Y.push_back(get(i, j));
		colOr.push_back(add_or(Y));
	}

	xSweep[0] = add_or({colOr[0]});
	xs1[0] = createInt(0, zero, xSweep[0]);
	for (int j = 1; j < W; j++) {
		xSweep[j] = add_or({colOr[j], xSweep[j-1]});
		xs1[j] = createInt(j, zero, add_xor({xSweep[j-1], xSweep[j]}));
	}

	rxSweep[W-1] = add_or({colOr[W-1]});
	xs2[W-1] = createInt(W-1, zero, rxSweep[W-1]);
	for (int j = W-2; j >= 0; j--) {
		rxSweep[j] = add_or({colOr[j], rxSweep[j+1]});
		xs2[j] = createInt(j, zero, add_xor({rxSweep[j+1], rxSweep[j]}));
	}

	BITINT y1 = orInt(ys1);
	BITINT y2 = orInt(ys2);
	BITINT x1 = orInt(xs1);
	BITINT x2 = orInt(xs2);

	equal(addInt(addInt(x1, y1), doCreateInt(K, zero)), addInt(x2, y2));
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 420 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB WA in grader: Invalid index
18 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 420 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB WA in grader: Invalid index
18 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 420 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB WA in grader: Invalid index
18 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 420 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB WA in grader: Invalid index
18 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 3 ms 728 KB Output is correct
3 Correct 2 ms 728 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 780 KB Output is correct
6 Correct 3 ms 728 KB Output is correct
7 Correct 2 ms 728 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 728 KB Output is correct
10 Correct 2 ms 728 KB Output is correct
11 Correct 2 ms 728 KB Output is correct
12 Correct 2 ms 812 KB Output is correct
13 Correct 2 ms 728 KB Output is correct
14 Correct 2 ms 808 KB Output is correct
15 Correct 3 ms 960 KB Output is correct
16 Correct 4 ms 724 KB Output is correct
17 Correct 3 ms 728 KB Output is correct
18 Correct 2 ms 984 KB Output is correct
19 Correct 3 ms 724 KB Output is correct
20 Correct 2 ms 728 KB Output is correct
21 Incorrect 0 ms 348 KB WA in grader: Invalid index
22 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 4 ms 860 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 2 ms 728 KB Output is correct
14 Correct 2 ms 728 KB Output is correct
15 Correct 3 ms 728 KB Output is correct
16 Correct 2 ms 808 KB Output is correct
17 Correct 2 ms 984 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Correct 2 ms 728 KB Output is correct
20 Correct 4 ms 1372 KB Output is correct
21 Correct 4 ms 1372 KB Output is correct
22 Correct 7 ms 1372 KB Output is correct
23 Correct 5 ms 1368 KB Output is correct
24 Correct 5 ms 1372 KB Output is correct
25 Correct 5 ms 1372 KB Output is correct
26 Correct 5 ms 1372 KB Output is correct
27 Correct 15 ms 1848 KB Output is correct
28 Correct 15 ms 2004 KB Output is correct
29 Correct 15 ms 1748 KB Output is correct
30 Correct 14 ms 2004 KB Output is correct
31 Correct 8 ms 2004 KB Output is correct
32 Incorrect 1 ms 348 KB WA in grader: Invalid index
33 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2004 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 2 ms 728 KB Output is correct
6 Correct 2 ms 816 KB Output is correct
7 Correct 4 ms 1372 KB Output is correct
8 Correct 5 ms 1372 KB Output is correct
9 Correct 8 ms 1908 KB Output is correct
10 Incorrect 1 ms 348 KB WA in grader: Invalid index
11 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 420 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB WA in grader: Invalid index
18 Halted 0 ms 0 KB -