Submission #979066

#	Time	Username	Problem	Language	Result	Execution time	Memory
979066		yhkhoo	Vision Program (IOI19_vision)	C++17	66 / 100	30 ms	1240 KiB

vision

#include "vision.h"
using namespace std;

#define pb push_back

void construct_network1(int H, int W, int K){
	vector<int> Ns;
	for(int i=0; i<1; i++){
		vector<int> sex;
		for(int j=i+1; j<H*W; j++){
			if(abs(i/W - j/W) + abs(i%W - j%W) == K){
				sex.push_back(j);
			}
		}
		if(sex.size()){
			Ns.push_back(add_and({i, add_or(sex)}));
		}
	}
	add_or(Ns);
}

void construct_network2(int H, int W, int K) {
	vector<int> Ns;
	for(int i=0; i<H*W; i++){
		vector<int> sex;
		for(int j=0; j<i; j++){
			if(abs(i/W - j/W) + abs(i%W - j%W) == K){
				sex.push_back(j);
			}
		}
		if(sex.size()){
			Ns.push_back(add_and({i, add_or(sex)}));
		}
	}
	add_or(Ns);
}

void construct_network3(int H, int W, int K) {
	if(H*W == 2){
		add_or({0, 1});
		return;
	}
	int hw = add_and({0, 1, 2});
	vector<int> wv;
	for(int i=0; i<W; i++){
		vector<int> wt;
		for(int j=0; j<H; j++){
			wt.pb(i+j*W);
		}
		wv.pb(add_or(wt));
	}
	vector<int> hv;
	for(int i=0; i<H; i++){
		vector<int> ht;
		for(int j=0; j<W; j++){
			ht.pb(i*W+j);
		}
		hv.pb(add_or(ht));
	}
	vector<int> wd;
	wd.pb(add_xor(wv));
	for(int i=1; i<=K; i++){
		vector<int> kwv;
		for(int j=0; j<W-i; j++){
			kwv.pb(add_and({wv[j], wv[j+i]}));
		}
		if(kwv.size()){
			wd.pb(add_or(kwv));
		}
		else{
			wd.pb(hw);
		}
	}
	vector<int> hd;
	hd.pb(add_xor(hv));
	for(int i=1; i<=K; i++){
		vector<int> khv;
		for(int j=0; j<H-i; j++){
			khv.pb(add_and({hv[j], hv[j+i]}));
		}
		if(khv.size()){
			hd.pb(add_or(khv));
		}
		else{
			hd.pb(hw);
		}
	}
	vector<int> fv;
	for(int i=0; i<=K; i++){
		fv.pb(add_and({wd[i], hd[K-i]}));
	}
	add_or(fv);
}

void construct_network(int H, int W, int K){
	if(H*W < 5000) construct_network2(H, W, K);
	else if((H+W)*K < 5000) construct_network3(H, W, K);
	else construct_network1(H, W, K);
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 0 / 19