Submission #145459

#	Time	Username	Problem	Language	Result	Execution time	Memory
145459		kingpig9	Vision Program (IOI19_vision)	C++14	100 / 100	39 ms	4344 KiB

vision

#include <bits/stdc++.h>
#include "vision.h"

using namespace std;
const int MAXN = 410;

int N, M, K;
int ncoord, npair;
vector<int> xtoy[MAXN], _ytox[MAXN], *ytox;
int xmin, xmax, ymin, ymax;

//position of x, y in the grid
//precondition: y is in xtoy[x]
int getgrid (int x, int y) {
	if ((x & 1) != (y & 1)) {
		assert(!"x and y have different parity");
	}
	int i = (x + y) / 2, j = (x - y) / 2;
	assert(0 <= i && i < N);
	assert(0 <= j && j < M);
	return M * i + j;
}

int getcoord (int nncoord = 0, int nnpair = 0, int offset = 0) {
	return N*M + nncoord * ncoord + nnpair * npair + offset;
}

int getindx (int mn, int x) {
	return mn + x;
}

int getindy (int mn, int y) {
	return mn + y + M - 1;
}

vector<int> getrange (int x, int y) {
	//exclusive
	vector<int> v;
	for (int i = x; i < y; i++) {
		v.push_back(i);
	}
	return v;
}

void construct_network (int nnn, int mmm, int kkk) {
	N = nnn;
	M = mmm;
	K = kkk;
	ncoord = N + M - 1;
	npair = ncoord - K;
	/*
	std::vector<int> Ns;
	Ns = {0, 1};
	int a = add_and(Ns);
	Ns = {0, a};
	int b = add_or(Ns);
	Ns = {0, 1, b};
	int c = add_xor(Ns);
	add_not(c);
	*/

	xmin = 0;
	xmax = N + M - 2;
	ymin = -(M - 1);
	ymax = N - 1;
	ytox = _ytox + (M - 1);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int x = i + j, y = i - j;
			xtoy[x].push_back(y);
			ytox[y].push_back(x);
		}
	}

	//"OR" of the ones w/x-coord = x
	int start1 = N*M, quant1 = ncoord;
	for (int x = xmin; x <= xmax; x++) {
		vector<int> v;
		for (int y : xtoy[x]) {
			v.push_back(getgrid(x, y));
		}
		add_or(v);
	}

	int start2 = start1 + quant1, quant2 = ncoord;
	for (int y = ymin; y <= ymax; y++) {
		vector<int> v;
		for (int x : ytox[y]) {
			v.push_back(getgrid(x, y));
		}
		add_or(v);
	}

	int start3 = start2 + quant2, quant3 = ncoord;
	for (int x = xmin; x <= xmax; x++) {
		vector<int> v;
		for (int y : xtoy[x]) {
			v.push_back(getgrid(x, y));
		}
		add_xor(v);
	}

	int start4 = start3 + quant3, quant4 = ncoord;
	for (int y = ymin; y <= ymax; y++) {
		vector<int> v;
		for (int x : ytox[y]) {
			v.push_back(getgrid(x, y));
		}
		add_xor(v);
	}

	int start5 = start4 + quant4, quant5 = npair;
	for (int x = xmin; x + K <= xmax; x++) {
		add_and({getindx(start1, x), getindx(start1, x + K)});
	}

	int start6 = start5 + quant5, quant6 = npair;
	for (int y = ymin; y + K <= ymax; y++) {
		add_and({getindy(start2, y), getindy(start2, y + K)});
	}

	int start7 = start6 + quant6, quant7 = npair;
	for (int x = xmin; x + K <= xmax; x++) {
		vector<int> v;
		for (int i = 0; i <= K; i++) {
			v.push_back(getindx(start1, x + i));
		}
		add_or(v);
	}

	int start8 = start7 + quant7, quant8 = npair;
	for (int y = ymin; y + K <= ymax; y++) {
		vector<int> v;
		for (int i = 0; i <= K; i++) {
			v.push_back(getindy(start2, y + i));
		}
		add_or(v);
	}

	int start9 = start8 + quant8, quant9 = npair;
	for (int x = xmin; x + K <= xmax; x++) {
		vector<int> v;
		for (int i = 0; i <= K; i++) {
			v.push_back(getindx(start3, x + i));
		}
		add_xor(v);
	}

	int start10 = start9 + quant9, quant10 = npair;
	for (int y = ymin; y + K <= ymax; y++) {
		vector<int> v;
		for (int i = 0; i <= K; i++) {
			v.push_back(getindy(start4, y + i));
		}
		add_xor(v);
	}

	int start11 = start10 + quant10, quant11 = npair;
	for (int x = xmin; x + K <= xmax; x++) {
		add_not(getindx(start9, x));
	}

	int start12 = start11 + quant11, quant12 = npair;
	for (int y = ymin; y + K <= ymax; y++) {
		add_not(getindy(start10, y));
	}
	
	int start13 = start12 + quant12, quant13 = npair;
	for (int x = xmin; x + K <= xmax; x++) {
		add_and({getindx(start7, x), getindx(start11, x)});
	}

	int start14 = start13 + quant13, quant14 = npair;
	for (int y = ymin; y + K <= ymax; y++) {
		add_and({getindy(start8, y), getindy(start12, y)});
	}

	int start15 = start14 + quant14, quant15 = 1;
	add_or(getrange(start13, start14));

	int start16 = start15 + quant15, quant16 = 1;
	add_or(getrange(start14, start15));
	
	int start17 = start16 + quant16, quant17 = 1;
	add_and({start15, start16});

	int start18 = start17 + quant17, quant18 = 1;
	add_or(getrange(start5, start7));

	int start19 = start18 + quant18, quant19 = 1;
	add_and({start17, start18});
}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:191:6: warning: unused variable 'start19' [-Wunused-variable]
  int start19 = start18 + quant18, quant19 = 1;
      ^~~~~~~
vision.cpp:191:35: warning: unused variable 'quant19' [-Wunused-variable]
  int start19 = start18 + quant18, quant19 = 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