IOI 2019 Vision Program

서브태스크 1,2,3,5,6: 가능한 K 거리의 쌍을 and로 묶은 뒤, and한 값들올 or로 묶어주면 된다.

만점 풀이: K 거리가 아니라 K 이상 거리만큼 떨어져 있는지 판별해 보자. 그러면 K 이상^K+1 이상으로 정답을 구할 수 있다. 답이 K 이상인지는 i+j가 K 차이나는 것이 있는지 or i-j가 K 차이나는 것이 있는지를 판별하면 되고, 이는 i+j가 k인 것이 있으면서, k-K 이하인 것이 있거나, k+K 이상인 것이 있는지 or i-j에 대해서 같은 게 있는지 판별하면 되고, 이는 i+j, i-j를 바탕으로 한 부분합으로 할 수 있다.

#include "vision.h"
#include <algorithm>
using namespace std;
int pval[401];
int mval[401];
int ppsum[401];
int pmsum[401];
int mpsum[401];
int mmsum[401];
vector<int>pgro[401];
vector<int>mgro[401];
int HH;
int WW;
int cu = 0;
int pos(int a, int b)
{
	return a * WW + b;
}
int isposs(int n)
{
	vector<int>x;
	int i;
	for (i = 0; i < HH + WW - 1-n; i++)
	{
		x.push_back(add_and({ pval[i], pmsum[i + n] }));
	}
	for (i = 0; i < HH + WW - 1 - n; i++)
	{
		x.push_back(add_and({ mval[i], mmsum[i + n] }));
	}
	for (i = n; i < HH + WW - 1; i++)
	{
		x.push_back(add_and({ pval[i], ppsum[i - n] }));
	}
	for (i = n; i < HH + WW - 1; i++)
	{
		x.push_back(add_and({ mval[i], mpsum[i - n] }));
	}
	return add_or(x);
}
void construct_network(int H, int W, int K) 
{
	HH = H;
	WW = W;
	int i, j;
	for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
		{
			pgro[i + j].push_back(pos(i, j));
			mgro[i - j + W - 1].push_back(pos(i, j));
		}
	}
	for (i = 0; i < H + W - 1; i++)
	{
		pval[i] = add_or(pgro[i]);
		mval[i] = add_or(mgro[i]);
	}
	ppsum[0] = pval[0];
	for (i = 1; i < H + W - 1; i++)
	{
		ppsum[i] = add_or({ ppsum[i - 1],pval[i] });
	}
	mpsum[0] = mval[0];
	for (i = 1; i < H + W - 1; i++)
	{
		mpsum[i] = add_or({ mpsum[i - 1],mval[i] });
	}
	pmsum[H+W-2] = pval[H+W-2];
	for (i = H+W-3; i >=0; i--)
	{
		pmsum[i] = add_or({ pmsum[i + 1],pval[i] });
	}
	mmsum[H + W - 2] = mval[H + W - 2];
	for (i = H + W - 3; i >= 0; i--)
	{
		mmsum[i] = add_or({ mmsum[i + 1],mval[i] });
	}
	int fi = isposs(K);
	if (K == H + W - 2)
		return;
	int se = isposs(K+1);
	add_xor({ fi,se });
}