Submission #549315

#	Time	Username	Problem	Language	Result	Execution time	Memory
549315		jesus_coconut	Vision Program (IOI19_vision)	C++17	100 / 100	18 ms	1608 KiB

vision

#include <bits/stdc++.h>
#include "vision.h"
#define pb push_back
#define eb emplace_back

using namespace std;

int h, w, k;

void consLine(int H, int W, int K) {
	vector<int> v;
	for (int i = 0; i + K < max(H, W); ++i) {
		v.pb(add_and({i, i + K}));
	}
	add_or(v);
}

vector<int> getRows() {
	vector<int> ret(h);
	vector<int> tmp(w);
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			tmp[j] = w * i + j;
		}
		ret[i] = add_xor(tmp);
	}
	return ret;
}

vector<int> getCols() {
	vector<int> ret(w), tmp(h);
	for (int j = 0; j < w; ++j) {
		for (int i = 0; i < h; ++i) {
			tmp[i] = w * i + j;
		}
		ret[j] = add_xor(tmp);
	}
	return ret;
}

void solvek1() {
	auto rows = getRows();
	auto cols = getCols();
	vector<int> adjRows, adjCols;
	for (int i = 0; i + 1 < size(rows); ++i) adjRows.eb(add_and({rows[i], rows[i+1]}));
	for (int i = 0; i + 1 < size(cols); ++i) adjCols.eb(add_and({cols[i], cols[i+1]}));
	int x = add_or(adjRows);
	int y = add_or(adjCols);
	int a = add_xor({x, y});
	int z1 = add_xor(rows);
	int z2 = add_xor(cols);
	int b = add_xor({z1, z2});
	add_and({a, b});
}

vector<int> pref_xor(vector<int> const &v) {
	vector<int> ret;
	ret.pb(v.front());
	for (int i = 1; i < size(v); ++i) {
		ret.pb(add_xor({v[i], ret[i - 1]}));
	}
	return ret;
}

int zero;

vector<int> calcSum(vector<int> &a, vector<int> &b) {
	vector<int> ret;
	int carry = zero;
	a.resize(max(size(a), size(b)), zero);
	b.resize(max(size(a), size(b)), zero);
	for (int i = 0; i < size(a); ++i) {
		ret.pb(add_xor({a[i], b[i], carry}));
		int tmp = add_or({a[i], b[i], carry});
		int tmp2 = add_and({a[i], b[i], carry});
		int nb = add_not(ret.back());
		int tmp3 = add_or({tmp2, nb});
		carry = add_and({tmp, tmp3});
	}
	ret.pb(carry);
	return ret;
}

vector<int> getSum(vector<int> const &v, int l, int r) {
	if (r - l == 1) return {v[l]};
	if (r - l <= 0) return {zero};
	int m = (r + l) / 2;
	auto x = getSum(v, l, m);
	auto y = getSum(v, m, r);
	return calcSum(x, y);
}


void construct_network(int H, int W, int K) {
	h = H;
	w = W;
	k = K;
	if (min(H, W) == 1) {
		consLine(H, W, K);
		return;
	}
	int tmp = add_not(0);
	zero = add_and({0, tmp});
	auto v = pref_xor(getRows());
	for (auto a : pref_xor(getCols())) v.pb(a);
	auto s = getSum(v, 0, size(v));
	for (int i = 0; i < size(s); ++i) {
		if (((k >> i) & 1) == 0) {
			s[i] = add_not(s[i]);
		}
	}
	add_and(s);
}

Compilation message (stderr)

vision.cpp: In function 'void solvek1()':
vision.cpp:45:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0; i + 1 < size(rows); ++i) adjRows.eb(add_and({rows[i], rows[i+1]}));
      |                  ~~~~~~^~~~~~~~~~~~
vision.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = 0; i + 1 < size(cols); ++i) adjCols.eb(add_and({cols[i], cols[i+1]}));
      |                  ~~~~~~^~~~~~~~~~~~
vision.cpp: In function 'std::vector<int> pref_xor(const std::vector<int>&)':
vision.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 1; i < size(v); ++i) {
      |                  ~~^~~~~~~~~
vision.cpp: In function 'std::vector<int> calcSum(std::vector<int>&, std::vector<int>&)':
vision.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 0; i < size(a); ++i) {
      |                  ~~^~~~~~~~~
vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (int i = 0; i < size(s); ++i) {
      |                  ~~^~~~~~~~~

• 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