Submission #807170

#	Time	Username	Problem	Language	Result	Execution time	Memory
807170		FEDIKUS	Vision Program (IOI19_vision)	C++17	100 / 100	91 ms	8048 KiB

vision

#include "vision.h"
#include<iostream>
#include<vector>
#include<utility>
#include<cassert>

using namespace std;

int h,w;
int tru;
vector<pair<int,int> > pdij;
vector<pair<int,int> > mdij;

int polje(int i,int j){
	return i*w+j;
}

int mjed(int k){
	vector<int> sve;
	for(auto _:pdij){
		vector<int> ne;
		auto [p,gate]=_;
		for(auto j:pdij){
			if(p-j.first>k || -p+j.first>k){
				ne.push_back(j.second);
			}
		}
		if(ne.empty()) continue;
		int neka=add_or(ne);
		sve.push_back(add_and({neka,gate}));
	}
	for(auto _:mdij){
		vector<int> ne;
		auto [m,gate]=_;
		for(auto j:mdij){
			if(m-j.first>k || -m+j.first>k){
				ne.push_back(j.second);
			}
		}
		if(ne.empty()) continue;
		int neka=add_or(ne);
		sve.push_back(add_and({neka,gate}));
	}
	if(sve.empty()) return tru;
	return add_not(add_or(sve));
}

void construct_network(int _h,int _w,int k){
	h=_h; w=_w;
	vector<int> tmp;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			tmp.push_back(polje(i,j));
		}
	}
	tru=add_or(tmp);
	for(int p=0;p<=h+w-2;p++){
		vector<int> dij;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(i+j==p){
					dij.push_back(polje(i,j));
				}
			}
		}
		assert(!dij.empty());
		pdij.push_back({p,add_or(dij)});
	}
	for(int m=-w+1;m<=h-1;m++){
		vector<int> dij;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(i-j==m){
					dij.push_back(polje(i,j));
				}
			}
		}
		mdij.push_back({m,add_or(dij)});
	}
	add_xor({mjed(k-1),mjed(k)});
}

• 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