Submission #248640

#	Time	Username	Problem	Language	Result	Execution time	Memory
248640		ChrisT	Vision Program (IOI19_vision)	C++17	100 / 100	40 ms	3864 KiB

vision

#include<bits/stdc++.h>
#include "vision.h"
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using pll = pair<ll,ll>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using ld = long double;
using ui = unsigned int;
using ull = unsigned long long;
using ui128 = __uint128_t;
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define lc ind<<1
#define rc ind<<1|1
const int MN = 1e5 + 2, LOG = 21, INF = 1e8;
int cur;
int _add_not (int n) {cur++; return add_not(n);}
int _add_and (vector<int> ns) {cur++; return add_and(ns);}
int _add_or (vector<int> ns) {cur++; return add_or(ns);}
int _add_xor (vector<int> ns) {cur++; return add_xor(ns);}
int check_k (int n, int m, int k) {
	vector<pii> check;
	int pbase = -1, sbase = -1;
	for (int nx = 2; nx + k <= n + m; nx++) {
		vector<int> on;
		for (int x = max(1,nx - m); x <= min(n,nx-1); x++) {
			int y = nx - x;
			on.push_back((x - 1) * m + y - 1);
		}
		if (~pbase) {on.push_back(cur-1); _add_or(on);}
		else pbase = _add_or(on);
	}
	for (int nx = n + m; nx - k >= 2; nx--) {
		vector<int> on;
		for (int x = max(1,nx-m); x <= min(n,nx-1); x++) {
			int y = nx - x;
			on.push_back((x-1) * m + y - 1);
		}
		if (~sbase) {on.push_back(cur-1); _add_or(on);}
		else sbase = _add_or(on);
		check.emplace_back(cur-1,pbase + nx - k - 2);
	}
	pbase = sbase = -1;
	for (int ny = 1 - n; ny + k <= m - 1; ny++) {
		vector<int> on; 
		for (int x = max(1,1 - ny); x <= min(n, m - ny); x++) {
			int y = ny + x;
			on.push_back((x-1) * m + y - 1);
		}
		if (~pbase) {on.push_back(cur-1); _add_or(on);}
		else pbase = _add_or(on);
	}
	for (int ny = m-1; ny - k >= 1 - n; ny--) {
		vector<int> on;
		for (int x = max(1,1 - ny); x <= min(n,m - ny); x++) {
			int y = ny + x;
			on.push_back((x-1) * m + y - 1);
		}
		if (~sbase) {on.push_back(cur-1); _add_or(on);}
		else sbase = _add_or(on);
		check.emplace_back(cur - 1, pbase + ny - k + n - 1);
	}
	int start = cur;
	for (pii p : check) _add_and({p.first,p.second});
	vector<int> go;
	for (int i = start; i < cur; i++) go.push_back(i);
	assert(go.size());
	return _add_or(go);
}
void construct_network (int n, int m, int k) { //(x,y) -> (x+y,x-y)
	cur = n * m;
	if (n + m - 2 == k) check_k(n,m,k);
	else _add_and({check_k(n,m,k),_add_not(check_k(n,m,k+1))});
}

• 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