Submission #164189

#	Time	Username	Problem	Language	Result	Execution time	Memory
164189		Anai	Vision Program (IOI19_vision)	C++14	100 / 100	15 ms	1780 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, BITS = 9;

struct State {
	int bits[BITS], inc; };

int rows[N], cols[N];
int ZERO, ONE;

static vector<int> make_op(int a, int b) {
	return (vector<int> {a, b}); }

static State make_state(int k = 0) {
	State res;
	if (k == 0) {
		for (int i = 0; i < BITS; ++i)
			res.bits[i] = ZERO;
		res.inc = ZERO; }
	else {
		for (int i = 0; i < BITS; ++i)
			res.bits[i] = (((1 << i) & k) ? ONE : ZERO);
		res.inc = ZERO; }
	return res; }


static State inc_if(State arg, int cond) {
	State res;
	int rem = cond;

	for (int i = 0; i < BITS; ++i) {
		res.bits[i] = add_xor(make_op(rem, arg.bits[i]));
		rem = add_and(make_op(rem, arg.bits[i]));
		if (i + 1 == BITS)
			break; }
	res.inc = cond;

	return res; }

static State add(State a, State b) {
	State ans;
	int rem = ZERO;
	for (int i = 0; i < BITS; ++i) {
		ans.bits[i] = add_xor(vector<int> {a.bits[i], b.bits[i], rem});
		rem = add_and(vector<int>{
			add_or({rem, a.bits[i]}),
			add_or({a.bits[i], b.bits[i]}),
			add_or({b.bits[i], rem}),
		});
	}
	ans.inc = ZERO;
	return ans; }

static int different(State a, State b) {
	int acc = ZERO;
	for (int i = 0; i < BITS; ++i)
		acc = add_or({add_xor({a.bits[i], b.bits[i]}), acc});
	return acc; }


void construct_network(int n, int m, int k) {
	ZERO = add_and(make_op(0, add_not(0)));
	ONE = add_not(ZERO);

	for (int i = 0; i < n; ++i) { // get rows
		vector<int> inp(m);
		iota(begin(inp), end(inp), i * m);
		rows[i] = add_xor(inp); }

	for (int j = 0; j < m; ++j) { // get cols
		vector<int> inp(n);
		for (int index = 0; index < n; ++index)
			inp[index] = index * m + j;
		cols[j] = add_xor(inp); }

	State row_dif = make_state();
	State col_dif = make_state();

	for (int i = 0; i < m; ++i)
		col_dif = inc_if(col_dif, add_xor({col_dif.inc, cols[i]}));
	for (int i = 0; i < n; ++i)
		row_dif = inc_if(row_dif, add_xor({row_dif.inc, rows[i]}));

	State ans = add(row_dif, col_dif);
	add_not(different(ans, make_state(k))); }

• 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