제출 #819396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
819396		andrey27_sm	Vision Program (IOI19_vision)	C++17	100 / 100	22 ms	2928 KiB

vision

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
int add_and(std::vector<int> Ns);

int add_or(std::vector<int> Ns);

int add_xor(std::vector<int> Ns);

int add_not(int N);


void construct_network(int H, int W, int K){
	// get_ver_or
	int BIT_NUM = 9;
	
	//int ZERO = add_and({0,1,2});
	int ZERO;
	if(H*W-1 >= 2) ZERO = add_and({0,1,2});
	else{
		if(K == 1) add_and({0,1});
		else add_not(0);
		return;
	}
	vector<int> dist_vert(BIT_NUM);
	vector<int> dist_hori(BIT_NUM);
	{
		vector<int> num_ones;
		for (int i = 0; i < W; ++i)
		{
			vector<int> tmp;
			for (int j = 0; j < H; ++j)
			{
				tmp.push_back(j*W+i);
			}
			num_ones.push_back(add_or(tmp));
		}
		vector<vector<int>> bits_to_next(W,vector<int>(BIT_NUM));
		for (int i = 0; i < W; ++i)
		{
			for (int bit = 0; bit < BIT_NUM; ++bit)
			{
				vector<int> tmp;
				for (int j = i+1; j < W; ++j)
				{
					int dist = j-i;
					if((dist>>bit)&1) tmp.push_back(num_ones[j]);
				}
				if(tmp.size()) bits_to_next[i][bit] = add_or(tmp);
				else bits_to_next[i][bit] = ZERO;
			}
		}
		vector<vector<int>> bits_to_next_anded(W,vector<int>(BIT_NUM));
		for (int i = 0; i < W; ++i)
		{
			for (int bit = 0; bit < BIT_NUM; ++bit)
			{
				bits_to_next_anded[i][bit] = add_and({bits_to_next[i][bit],num_ones[i]});
			}
		}
		for (int bit = 0; bit < BIT_NUM; ++bit)
		{
			vector<int> tmp;
			for (int i = 0; i < W; ++i)
			{
				tmp.push_back(bits_to_next_anded[i][bit]);
			}
			dist_vert[bit] = add_or(tmp);
		}
	}
	{
		vector<int> num_ones;
		for (int i = 0; i < H; ++i)
		{
			vector<int> tmp;
			for (int j = 0; j < W; ++j)
			{
				tmp.push_back(i*W+j);
			}
			num_ones.push_back(add_or(tmp));
		}
		vector<vector<int>> bits_to_next(H,vector<int>(BIT_NUM));
		for (int i = 0; i < H; ++i)
		{
			for (int bit = 0; bit < BIT_NUM; ++bit)
			{
				vector<int> tmp;
				for (int j = i+1; j < H; ++j)
				{
					int dist = j-i;
					if((dist>>bit)&1) tmp.push_back(num_ones[j]);
				}
				if(tmp.size()) bits_to_next[i][bit] = add_or(tmp);
				else bits_to_next[i][bit] = ZERO;
			}
		}

		vector<vector<int>> bits_to_next_anded(H,vector<int>(BIT_NUM));
		for (int i = 0; i < H; ++i)
		{
			for (int bit = 0; bit < BIT_NUM; ++bit)
			{
				bits_to_next_anded[i][bit] = add_and({bits_to_next[i][bit],num_ones[i]});
			}
		}
		for (int bit = 0; bit < BIT_NUM; ++bit)
		{
			vector<int> tmp;
			for (int i = 0; i < H; ++i)
			{
				tmp.push_back(bits_to_next_anded[i][bit]);
			}
			dist_hori[bit] = add_or(tmp);
		}
	}
	vector<int> delta(BIT_NUM,ZERO);
	vector<int> ans(BIT_NUM);
	for (int i = 0; i < BIT_NUM; ++i)
	{
		ans[i] = add_xor({delta[i],dist_hori[i],dist_vert[i]});
		if(i != BIT_NUM-1){
			int tmp_and = add_and({delta[i],dist_hori[i],dist_vert[i]});
			int tmp_not = add_not(ans[i]);
			int tmp_or = add_or({delta[i],dist_hori[i],dist_vert[i]});
			int tmp_or2 = add_or({tmp_not,tmp_and});
			delta[i+1] = add_and({tmp_or,tmp_or2});
		}
	}

	vector<int> ans_check(BIT_NUM);
	for (int i = 0; i < BIT_NUM; ++i)
	{
		int target = (K>>i)&1;
		if(target) ans_check[i] = add_or({ans[i]});
		else ans_check[i] = add_not(ans[i]);
	}

	int ans_end = add_and(ans_check);
}

컴파일 시 표준 에러 (stderr) 메시지

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:139:6: warning: unused variable 'ans_end' [-Wunused-variable]
  139 |  int ans_end = add_and(ans_check);
      |      ^~~~~~~

• 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