제출 #285659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285659		cookiedoth	Vision Program (IOI19_vision)	C++14	100 / 100	15 ms	1652 KiB

vision

#include "vision.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <deque>
#include <queue>
#include <algorithm>
#include <string>
#include <cassert>
#include <memory>
#include <numeric>
#include <functional>
#include <random>
#define ll long long
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define length(a) ((int)a.size())

using namespace std;

template<class iterator> void output(iterator begin, iterator end, ostream &out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(const T &x, ostream &out = cerr) {
	output(all(x), out);
}

template<class T> int chkmin(T &a, const T &b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmax(T &a, const T &b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

int ONE, ZERO;

vector<int> to_number(const vector<int> &A, int B) {
	vector<int> res;
	for (int b = 0; b < B; ++b) {
		vector<int> cur;
		for (int i = 0; i < A.size(); ++i) {
			if ((i >> b) & 1) {
				cur.push_back(A[i]);
			}
		}
		if (cur.empty()) {
			res.push_back(ZERO);
		} else {
			res.push_back(add_or(cur));
		}
	}
	return res;
}

void flip(vector<int> &a) {
	for (int i = 0; i < a.size(); ++i) {
		a[i] = add_not(a[i]);
	}
}

vector<int> sum(const vector<int> &a, const vector<int> &b) {
	int B = a.size();
	vector<int> res(B);
	int p = -1;
	for (int i = 0; i < B; ++i) {
		if (p == -1) {
			res[i] = add_xor({a[i], b[i]});
			p = add_and({a[i], b[i]});
		} else {
			res[i] = add_xor({a[i], b[i], p});
			p = add_or({add_and({a[i], b[i]}), add_and({a[i], p}), add_and({b[i], p})});
		}
	}
	return res;
}

vector<int> from_bits(const vector<int> &a, int n, int B) {
	vector<int> res(n);
	for (int i = 0; i < n; ++i) {
		vector<int> cur;
		for (int j = 0; j < B; ++j) {
			if ((i >> j) & 1) {
				cur.push_back(a[j]);
			} else {
				cur.push_back(add_not(a[j]));
			}
		}
		res[i] = add_and(cur);
	}
	return res;
}

vector<int> substract_from(const vector<int> &a) {
	int p = ZERO;
	vector<int> res(a.size());
	for (int i = 0; i < a.size(); ++i) {
		res[i] = add_xor({a[i], p});
		p = add_or({a[i], p});
	}
	return res;
}

vector<int> diff(const vector<int> &R, const vector<int> &L) {
	int n = R.size();
	int B = 1;
	while ((1 << B) < n) {
		B++;
	}
	// cerr << "kek" << endl;
	vector<int> num1 = to_number(R, B);
	vector<int> num2 = to_number(L, B);
	num2 = substract_from(num2);
	// cerr << "num1" << endl;
	// output(all(num1));
	// cerr << "num2" << endl;
	// output(all(num2));
	// cerr << "_num2" << endl;
	// output(all(num2));
	vector<int> res = sum(num1, num2);
	// cerr << "_res" << endl;
	// output(all(res));
	// cerr << "res" << endl;
	// output(all(res));
	vector<int> res_diff = from_bits(res, n, B);
	return res_diff;
}

vector<int> diff(const vector<int> &a) {
	// cerr << "diff" << endl;
	// output(all(a));
	int n = a.size();
	vector<int> pref(n), suf(n);
	pref[0] = add_not(a[0]);
	for (int i = 1; i < n; ++i) {
		pref[i] = add_and({add_not(a[i]), pref[i - 1]});
	}
	suf[n - 1] = add_not(a[n - 1]);
	for (int i = n - 2; i >= 0; --i) {
		suf[i] = add_and({add_not(a[i]), suf[i + 1]});
	}
	vector<int> L(n), R(n);
	L[0] = a[0];
	for (int i = 1; i < n; ++i) {
		L[i] = add_and({a[i], pref[i - 1]});
	}
	R[n - 1] = a[n - 1];
	for (int i = n - 2; i >= 0; --i) {
		R[i] = add_and({a[i], suf[i + 1]});
	}
	// cerr << "LR = " << endl;
	// output(all(L));
	// output(all(R));
	return diff(R, L);
}

int n, m, k;

int get(int r, int c) {
	return r * m + c;
}

void construct_network(int _n, int _m, int _k) {
	n = _n;
	m = _m;
	k = _k;
	ONE = add_or({0, add_not(0)});
	ZERO = add_and({0, add_not(0)});
	vector<int> rows, columns;
	for (int i = 0; i < n; ++i) {
		vector<int> cur_row;
		for (int j = 0; j < m; ++j) {
			cur_row.push_back(get(i, j));
		}
		rows.push_back(add_or(cur_row));
	}
	for (int i = 0; i < m; ++i) {
		vector<int> cur_column;
		for (int j = 0; j < n; ++j) {
			cur_column.push_back(get(j, i));
		}
		columns.push_back(add_or(cur_column));
	}
	// cerr << "rows" << endl;
	// output(all(rows));
	// cerr << "columns" << endl;
	// output(all(columns));
	vector<int> row_d = diff(rows);
	vector<int> col_d = diff(columns);
	// cerr << "row_d" << endl;
	// output(all(row_d));
	// cerr << "col_d" << endl;
	// output(all(col_d));
	vector<int> poss;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i + j == k) {
				poss.push_back(add_and({row_d[i], col_d[j]}));
			}
		}
	}
	add_or(poss);
}

컴파일 시 표준 에러 (stderr) 메시지

vision.cpp: In function 'std::vector<int> to_number(const std::vector<int>&, int)':
vision.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int i = 0; i < A.size(); ++i) {
      |                   ~~^~~~~~~~~~
vision.cpp: In function 'void flip(std::vector<int>&)':
vision.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for (int i = 0; i < a.size(); ++i) {
      |                  ~~^~~~~~~~~~
vision.cpp: In function 'std::vector<int> substract_from(const std::vector<int>&)':
vision.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for (int i = 0; i < a.size(); ++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