Submission #838420

#	Time	Username	Problem	Language	Result	Execution time	Memory
838420		GusterGoose27	Vision Program (IOI19_vision)	C++17	100 / 100	11 ms	1364 KiB

vision

#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 (stderr)

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 / 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