oj.uz

Submission #838420

# Submission time Handle Problem Language Result Execution time Memory
838420 2023-08-26T20:37:38 Z GusterGoose27 Vision Program (IOI19_vision) C++17
100 / 100
 11 ms 1364 KB 
#include <bits/stdc++.h>
#include "vision.h"

using namespace std;

int t;
int b;
int _0;

int AND(vector<int> v) {
	t++;
	return add_and(v);
}

int XOR(vector<int> v) {
	t++;
	return add_xor(v);
}

int OR(vector<int> v) {
	t++;
	return add_or(v);
}

int NOT(int v) {
	t++;
	return add_not(v);
}

void subtract(vector<int> &u, vector<int> &v, vector<int> &c) {
	assert(u.size() == b);
	assert(v.size() == b);
	int sub = _0;
	for (int i = 0; i < b; i++) {
		c.push_back(XOR({u[i], v[i], sub}));
		sub = OR({AND({sub, v[i]}), AND({OR({sub, v[i]}), NOT(u[i])})});
	}
}

void add(vector<int> &u, vector<int> &v, vector<int> &c) {
	assert(u.size() == b);
	assert(v.size() == b);
	int carry = _0;
	for (int i = 0; i < b; i++) {
		c.push_back(XOR({u[i], v[i], carry}));
		carry = OR({AND({u[i], carry}),
			AND({v[i], carry}),
			AND({u[i], v[i]})});
	}
	c.push_back(carry);
}

void print(string name, vector<int> &v) {
	cerr << name << ":";
	for (int i: v) cerr << ' ' << i;
	cerr << endl;
}

void make_single(int n, int s, vector<int> &res) {
	vector<int> l, r;
	int p = t;
	for (int i = 0; i < n; i++) {
		vector<int> v;
		v.push_back(s+i);
		if (i) v.push_back(p+i-1);
		// cerr << t << ": ";
		// for (int j: v) cerr << j << ' ';
		// cerr << '\n';
		XOR(v);
	}
	for (int i = 0; i < n; i++) {
		l.push_back(AND({p+i, s+i}));
		r.push_back(OR({AND({NOT(p+i), s+i}), AND({p+n-1, s+i})}));
	}
	// print("l", l);
	// print("r", r);
	// cerr << endl;
	vector<int> lpos, rpos;
	for (int i = 0; i < b; i++) {
		vector<int> vals[2];
		for (int j = 0; j < n; j++) {
			if (j&(1<<i)) {
				vals[0].push_back(l[j]);
				vals[1].push_back(r[j]);
			}
		}
		lpos.push_back(vals[0].empty() ? _0 : OR(vals[0]));
		rpos.push_back(vals[1].empty() ? _0 : OR(vals[1]));
	}
	// print("lpos", lpos);
	// print("rpos", rpos);
	subtract(rpos, lpos, res);
	// print("res", res);
}

void construct_network(int H, int W, int K) {
	int h = H, w = W, k = K;
	t = h*w;
	b = 32-__builtin_clz(max(h, w));
	// cerr << b << endl << endl;;
	_0 = AND({0, NOT(0)});
	// _1 = OR({0, NOT(0)});
	for (int i = 0; i < h; i++) {
		vector<int> v(w);
		iota(v.begin(), v.end(), w*i);
		OR(v);
	}
	vector<int> p1;
	make_single(h, t-h, p1);
	for (int i = 0; i < w; i++) {
		vector<int> v;
		for (int j = 0; j < h; j++) v.push_back(w*j+i);
		OR(v);
	}
	vector<int> p2;
	make_single(w, t-w, p2);
	vector<int> p3;
	add(p1, p2, p3); // stored with 0 bit first
	// print("sum", p3);
	vector<int> bit_comp; // should all be 1s
	for (int i = 0; i <= b; i++) {
		int cur = ((k & (1<<i)) == 0);
		bit_comp.push_back(cur ? NOT(p3[i]) : p3[i]);
	}
	AND(bit_comp);
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from vision.cpp:1:
vision.cpp: In function 'void subtract(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
vision.cpp:31:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |  assert(u.size() == b);
      |         ~~~~~~~~~^~~~
vision.cpp:32:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |  assert(v.size() == b);
      |         ~~~~~~~~~^~~~
vision.cpp: In function 'void add(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
vision.cpp:41:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |  assert(u.size() == b);
      |         ~~~~~~~~~^~~~
vision.cpp:42:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |  assert(v.size() == b);
      |         ~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 224 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 224 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 224 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 3 ms 596 KB Output is correct
39 Correct 1 ms 320 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 2 ms 468 KB Output is correct
42 Correct 2 ms 468 KB Output is correct
43 Correct 3 ms 596 KB Output is correct
44 Correct 3 ms 596 KB Output is correct
45 Correct 3 ms 596 KB Output is correct
46 Correct 3 ms 596 KB Output is correct
47 Correct 3 ms 596 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 532 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 5 ms 852 KB Output is correct
21 Correct 5 ms 852 KB Output is correct
22 Correct 5 ms 852 KB Output is correct
23 Correct 5 ms 852 KB Output is correct
24 Correct 5 ms 852 KB Output is correct
25 Correct 5 ms 852 KB Output is correct
26 Correct 5 ms 852 KB Output is correct
27 Correct 8 ms 1236 KB Output is correct
28 Correct 10 ms 1364 KB Output is correct
29 Correct 8 ms 1288 KB Output is correct
30 Correct 8 ms 1364 KB Output is correct
31 Correct 8 ms 1364 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1364 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 980 KB Output is correct
8 Correct 5 ms 852 KB Output is correct
9 Correct 8 ms 1256 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #8
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 224 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 3 ms 596 KB Output is correct
39 Correct 1 ms 320 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 2 ms 468 KB Output is correct
42 Correct 2 ms 468 KB Output is correct
43 Correct 3 ms 596 KB Output is correct
44 Correct 3 ms 596 KB Output is correct
45 Correct 3 ms 596 KB Output is correct
46 Correct 3 ms 596 KB Output is correct
47 Correct 3 ms 596 KB Output is correct
48 Correct 2 ms 340 KB Output is correct
49 Correct 2 ms 340 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 2 ms 340 KB Output is correct
54 Correct 1 ms 340 KB Output is correct
55 Correct 1 ms 340 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 1 ms 340 KB Output is correct
58 Correct 1 ms 340 KB Output is correct
59 Correct 1 ms 340 KB Output is correct
60 Correct 1 ms 340 KB Output is correct
61 Correct 1 ms 340 KB Output is correct
62 Correct 1 ms 340 KB Output is correct
63 Correct 1 ms 340 KB Output is correct
64 Correct 1 ms 340 KB Output is correct
65 Correct 1 ms 340 KB Output is correct
66 Correct 1 ms 340 KB Output is correct
67 Correct 2 ms 340 KB Output is correct
68 Correct 0 ms 212 KB Output is correct
69 Correct 0 ms 212 KB Output is correct
70 Correct 0 ms 212 KB Output is correct
71 Correct 0 ms 212 KB Output is correct
72 Correct 1 ms 340 KB Output is correct
73 Correct 1 ms 340 KB Output is correct
74 Correct 1 ms 340 KB Output is correct
75 Correct 1 ms 340 KB Output is correct
76 Correct 1 ms 340 KB Output is correct
77 Correct 2 ms 468 KB Output is correct
78 Correct 2 ms 468 KB Output is correct
79 Correct 2 ms 468 KB Output is correct
80 Correct 2 ms 532 KB Output is correct
81 Correct 2 ms 468 KB Output is correct
82 Correct 1 ms 340 KB Output is correct
83 Correct 1 ms 340 KB Output is correct
84 Correct 1 ms 340 KB Output is correct
85 Correct 1 ms 340 KB Output is correct
86 Correct 1 ms 340 KB Output is correct
87 Correct 1 ms 340 KB Output is correct
88 Correct 1 ms 340 KB Output is correct
89 Correct 5 ms 852 KB Output is correct
90 Correct 5 ms 852 KB Output is correct
91 Correct 5 ms 852 KB Output is correct
92 Correct 5 ms 852 KB Output is correct
93 Correct 5 ms 852 KB Output is correct
94 Correct 5 ms 852 KB Output is correct
95 Correct 5 ms 852 KB Output is correct
96 Correct 8 ms 1236 KB Output is correct
97 Correct 10 ms 1364 KB Output is correct
98 Correct 8 ms 1288 KB Output is correct
99 Correct 8 ms 1364 KB Output is correct
100 Correct 8 ms 1364 KB Output is correct
101 Correct 0 ms 212 KB Output is correct
102 Correct 0 ms 212 KB Output is correct
103 Correct 8 ms 1364 KB Output is correct
104 Correct 0 ms 212 KB Output is correct
105 Correct 1 ms 340 KB Output is correct
106 Correct 2 ms 468 KB Output is correct
107 Correct 1 ms 340 KB Output is correct
108 Correct 1 ms 340 KB Output is correct
109 Correct 6 ms 980 KB Output is correct
110 Correct 5 ms 852 KB Output is correct
111 Correct 8 ms 1256 KB Output is correct
112 Correct 0 ms 212 KB Output is correct
113 Correct 0 ms 212 KB Output is correct
114 Correct 8 ms 1360 KB Output is correct
115 Correct 1 ms 340 KB Output is correct
116 Correct 1 ms 428 KB Output is correct
117 Correct 5 ms 852 KB Output is correct
118 Correct 5 ms 852 KB Output is correct
119 Correct 8 ms 1264 KB Output is correct
120 Correct 10 ms 1348 KB Output is correct
121 Correct 8 ms 1364 KB Output is correct
122 Correct 8 ms 1352 KB Output is correct
123 Correct 11 ms 1364 KB Output is correct
124 Correct 8 ms 1332 KB Output is correct
125 Correct 8 ms 1364 KB Output is correct
126 Correct 8 ms 1364 KB Output is correct
127 Correct 8 ms 1332 KB Output is correct
128 Correct 8 ms 1328 KB Output is correct