Submission #1155340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155340		the_coding_pooh	Vision Program (IOI19_vision)	C++20	100 / 100	11 ms	2120 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
#define uwu return 0;

#define all(x) x.begin(), x.end()

using namespace std;

const int LOG_C = 8;

int my_not(int nt){
	if(nt == -1)
		return -2;
	if(nt == -2)
		return -1;
	return add_not(nt);
}

int my_or(vector <int> vec){
	vector <int> tmp;
	for (auto i : vec){
		if(i >= 0)
			tmp.push_back(i);
		if(i == -2)
			return -2;
	}
	if(tmp.empty())
		return -1;
	return add_or(tmp);
}

int my_xor(vector <int> vec){
	vector <int> tmp;
	int cnt = 0;
	for (auto i : vec){
		if(i >= 0)
			tmp.push_back(i);
		if(i == -2)
			cnt++;
	}
	if(tmp.empty())
		return (cnt & 1) ? -2 : -1;
	return cnt & 1 ? add_not(add_xor(tmp)) : add_xor(tmp);
}

int my_and(vector <int> vec){
	vector<int> tmp;
	for (auto i : vec){
		if(i >= 0)
			tmp.push_back(i);
		if(i == -1)
			return -1;
	}
	if(tmp.empty())
		return -2;
	return add_and(tmp);
}

int H, W;

int input_pin(int x, int y){
	return W * x + y;
}

vector <int> rev(vector <int> a){
	vector<int> ret;
	for (auto i : a){
		ret.push_back(my_not(i));
	}
	return ret;
}

vector <int> cnt_to_max(vector <int> cnt, vector <int> rev){
	int N = cnt.size();
	vector<int> ret;
	for (int i = 0; i < N; i++){
		vector <int> tmp;
		for (int j = i + 1; j < N; j++){
			tmp.push_back(rev[j]);
		}
		tmp.push_back(cnt[i]);
		ret.push_back(my_and(tmp));
	}
	return ret;
}

vector <int> cnt_to_min(vector <int> cnt, vector <int> rev){
	int N = cnt.size();
	vector<int> ret;
	for (int i = 0; i < N; i++){
		vector <int> tmp;
		for (int j = 0; j < i; j++){
			tmp.push_back(rev[j]);
		}
		tmp.push_back(cnt[i]);
		ret.push_back(my_and(tmp));
	}
	return ret;
}

vector <int> cnt_to_bin(vector <int> cnt){
	int N = cnt.size();
	vector<int> ret;
	for (int t = 0; t < LOG_C; t++){
		int bt = 1 << (LOG_C - t - 1);
		vector <int> tmp;
		for (int i = 0; i < N; i++){
			if(i & bt)
				tmp.push_back(cnt[i]);
		}
		ret.push_back(my_or(tmp));
	}
	return ret;
}

int check_two_in_three(int a, int b, int c){
	int ab = my_and({a, b}), bc = my_and({b, c}), ac = my_and({a, c});
	return my_or({ab, bc, ac});
}

vector <int> add(vector <int> a, vector<int> b){
	int carry = my_and({a.back(), b.back()});
	vector<int> ret = {my_xor({a.back(), b.back()})};
	a.pop_back(), b.pop_back();
	for (int t = 0; t < LOG_C; t++){
		if(a.empty()){
			ret.push_back(carry);
			continue;
		}
		ret.push_back(my_xor({carry, a.back(), b.back()}));
		carry = check_two_in_three(carry, a.back(), b.back());
		a.pop_back(), b.pop_back();
	}
	reverse(all(ret));
	return ret;
}

int check_less(int a, int b){
	int r = my_not(a);
	return my_and({r, b});
}

int check_same(int a, int b){
	int r = my_xor({a, b});
	return my_not(r);
}

int get_c(int c, int a, int b){
	int l = check_less(a, b), s = check_same(a, b), r = my_not(c);
	return my_or({my_and({c, l}), my_and({c, s}), my_and({r, l})});
}

vector <int> subtract(vector<int> a, vector<int> b){
	int carry = check_less(a.back(), b.back());
	vector<int> ret = {my_xor({a.back(), b.back()})};
	a.pop_back(), b.pop_back();
	for (int t = 0; t < LOG_C - 1; t++){
		ret.push_back(my_xor({carry, a.back(), b.back()}));
		carry = get_c(carry, a.back(), b.back());
		a.pop_back(), b.pop_back();
	}
	reverse(all(ret));
	return ret;
}

void copy(vector <int> a){
	for(auto i:a){
		my_and({i});
	}
	return;
}

void construct_network(int _H, int _W, int K) {
	H = _H, W = _W;
	vector <int> cnt_x(H), cnt_y(W);
	for (int i = 0; i < H; i++){
		vector <int> tmp;
		for (int j = 0; j < W; j++){
			tmp.push_back(input_pin(i, j));
		}
		cnt_x[i] = my_or(tmp);
	}
	for (int i = 0; i < W; i++){
		vector <int> tmp;
		for (int j = 0; j < H; j++){
			tmp.push_back(input_pin(j, i));
		}
		cnt_y[i] = my_or(tmp);
	}
	vector<int> rev_cnt_x = rev(cnt_x), rev_cnt_y = rev(cnt_y);
	vector<int> max_cnt_x = cnt_to_max(cnt_x, rev_cnt_x), min_cnt_x = cnt_to_min(cnt_x, rev_cnt_x);
	vector<int> max_cnt_y = cnt_to_max(cnt_y, rev_cnt_y), min_cnt_y = cnt_to_min(cnt_y, rev_cnt_y);
	vector<int> max_x = cnt_to_bin(max_cnt_x), min_x = cnt_to_bin(min_cnt_x);
	vector<int> max_y = cnt_to_bin(max_cnt_y), min_y = cnt_to_bin(min_cnt_y);
	vector<int> delta_x = subtract(max_x, min_x);
	vector<int> delta_y = subtract(max_y, min_y);
	vector<int> result = add(delta_x, delta_y);
	vector<int> rev_result = rev(result);
	vector<int> output_pin;
	for (int t = 0; t < LOG_C + 1; t++){
		int bt = 1 << (LOG_C - t);
		if(K & bt){
			output_pin.push_back(result[t]);
		}
		else
			output_pin.push_back(rev_result[t]);
	}
	copy(delta_x);
	copy(delta_y);
	copy(result);
	my_and(output_pin);
	return;
}

• 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