Submission #819388

# Submission time Handle Problem Language Result Execution time Memory
819388 2023-08-10T10:12:05 Z andrey27_sm Vision Program (IOI19_vision) C++17
0 / 100
18 ms 2888 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 = 10;
	int ZERO = add_and({0,1,2,4});
	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:131:6: warning: unused variable 'ans_end' [-Wunused-variable]
  131 |  int ans_end = add_and(ans_check);
      |      ^~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 1108 KB Output is correct
2 Correct 6 ms 1108 KB Output is correct
3 Correct 6 ms 1108 KB Output is correct
4 Correct 7 ms 1024 KB Output is correct
5 Correct 8 ms 1108 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 6 ms 1108 KB Output is correct
8 Correct 6 ms 1068 KB Output is correct
9 Correct 7 ms 1084 KB Output is correct
10 Correct 8 ms 1108 KB Output is correct
11 Correct 6 ms 1108 KB Output is correct
12 Correct 6 ms 1036 KB Output is correct
13 Correct 7 ms 1108 KB Output is correct
14 Correct 8 ms 1112 KB Output is correct
15 Correct 6 ms 1108 KB Output is correct
16 Correct 6 ms 1120 KB Output is correct
17 Correct 8 ms 1108 KB Output is correct
18 Correct 8 ms 1036 KB Output is correct
19 Correct 7 ms 1108 KB Output is correct
20 Correct 6 ms 1108 KB Output is correct
21 Incorrect 0 ms 212 KB WA in grader: Invalid index
22 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 18 ms 2888 KB Output is correct
2 Incorrect 0 ms 212 KB WA in grader: Invalid index
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -