Submission #1056551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056551		Tob	Vision Program (IOI19_vision)	C++14	100 / 100	6 ms	1764 KiB

vision

#include <bits/stdc++.h>

#include "vision.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int lg = 8;
int p[2];

vector <int> f(vector <int> v) {
	vector <int> v2;
	for (auto x : v) if (x != -1) v2.pb(x);
	return v2;
}

void add1(vector <int>& a, int ca) {
	for (int i = 0; i < lg; i++) {
		int y;
		if (a[i] != -1) y = add_and({a[i], ca});
		else y = p[0];
		a[i] = add_xor(f({a[i], ca}));
		ca = y;
	}
}

void add2(vector <int>& a, vector <int> b) {
	for (int i = 0, ca = -1; i < lg+1; i++) {
		vector <int> v1, v2;
		v1 = {a[i], b[i], ca};
		int x = add_xor(f(v1));
		if (ca == -1 && a[i] != -1 && b[i] != -1) ca = add_and({a[i], b[i]});
		v2 = f(v1);
		if (v2.size() < 2) ca = -1;
		else if (v2.size() == 2) ca = add_and(v2);
		else ca = add_or({add_and({v2[0],v2[1]}), add_and({v2[0],v2[2]}), add_and({v2[1],v2[2]})});
		a[i] = x;
	}
}

void construct_network(int h, int w, int k) {
	vector <int> pxh(h), pxw(w);
	vector <int> v, a, b, tmp;
	
	for (int i = 0; i < w; i++) v.pb(i);
	pxh[0] = add_xor(v);
	
	for (int i = 0; i < lg; i++) a.pb(-1);
	a[0] = pxh[0];
	tmp = {pxh[0]};
	
	for (int i = 1; i < h; i++) {
		v.clear(); for (int j = 0; j < w; j++) v.pb(i*w+j);
		v.pb(pxh[i-1]);
		pxh[i] = add_xor(v);
		tmp.pb(pxh[i]);
	}
	
	v.clear();
	for (int i = 0; i < h; i++) v.pb(i*w);
	pxw[0] = add_xor(v);
	
	for (int i = 0; i < lg; i++) b.pb(-1);
	b[0] = pxw[0];
	tmp.pb(pxw[0]);
	
	for (int i = 1; i < w; i++) {
		v.clear(); for (int j = 0; j < h; j++) v.pb(j*w+i);
		v.pb(pxw[i-1]);
		pxw[i] = add_xor(v);
		tmp.pb(pxw[i]);
	}
	
	p[1] = add_or(tmp); p[0] = add_not(p[1]);
	
	for (int i = 1; i < h; i++) add1(a, pxh[i]);
	for (int i = 1; i < w; i++) add1(b, pxw[i]);
	a.pb(-1); b.pb(-1);
	add2(a, b);
	
	v.clear();
	for (int i = 0; i < lg+1; i++) {
		int B = ((k >> i) & 1);
		v.pb(add_xor(f({p[B], a[i]})));
	}
	add_not(add_or(v));
}

• 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