답안 #819394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
819394 2023-08-10T10:14:50 Z andrey27_sm Vision Program (IOI19_vision) C++17
0 / 100
18 ms 2880 KB
#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);
}

Compilation message

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:20:22: warning: value computed is not used [-Wunused-value]
   20 |  if(H*W-1 >= 2) ZERO == add_and({0,1,2});
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~
vision.cpp:139:6: warning: unused variable 'ans_end' [-Wunused-variable]
  139 |  int ans_end = add_and(ans_check);
      |      ^~~~~~~
vision.cpp:51:31: warning: 'ZERO' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |     else bits_to_next[i][bit] = ZERO;
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1040 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 2880 KB Output is correct
2 Incorrect 0 ms 212 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
2 Halted 0 ms 0 KB -