Submission #601110

#	Time	Username	Problem	Language	Result	Execution time	Memory
601110		sofapuden	Vision Program (IOI19_vision)	C++14	100 / 100	49 ms	5228 KiB

vision

#include "vision.h"
#include<bits/stdc++.h>

using namespace std;

int h, w, k;

void pr(vector<int> v){
	cout << v.size() << '\n';
	for(auto x : v)cout << x/w << ' ' << x%w << '\n';
	cout << '\n';
}

void construct_network(int _h, int _w, int _k) {
	h = _h, w = _w, k = _k;
	int cnt = h*w-1;
	vector<int> rdiaxor, rdiaor, ldiaxor, ldiaor;
	for(int i = h-1; ~i; --i){
		vector<int> cu;
		for(int j = 0; i+j < h && j < w; ++j){
			cu.push_back((i+j)*w+j);
		}
		rdiaxor.push_back(++cnt);
		add_xor(cu);
		rdiaor.push_back(++cnt);
		add_or(cu);
	}
	for(int i = 1; i < w; ++i){
		vector<int> cu;
		for(int j = 0; i+j < w && j < h; ++j){
			cu.push_back(j*w+i+j);
		}
		rdiaxor.push_back(++cnt);
		add_xor(cu);
		rdiaor.push_back(++cnt);
		add_or(cu);
	}
	for(int i = 0; i < w; ++i){
		vector<int> cu;
		for(int j = 0; ~(i-j) && j < h; ++j){
			cu.push_back(j*w+i-j);
		}
		ldiaxor.push_back(++cnt);
		add_xor(cu);
		ldiaor.push_back(++cnt);
		add_or(cu);
	}
	for(int i = 1; i < h; ++i){
		vector<int> cu;
		for(int j = 0; i+j < h && j < w; ++j){
			cu.push_back((i+j)*w+w-j-1);
		}
		ldiaxor.push_back(++cnt);
		add_xor(cu);
		ldiaor.push_back(++cnt);
		add_or(cu);
	}
	auto f = [&](int k1)->void{
		vector<int> ans1, ans2;
		for(int i = 0; i < h+w-k1-1; ++i){
			vector<int> cu1, cu2;
			for(int j = 0; j <= k1; ++j){
				cu1.push_back(rdiaxor[i+j]);
				cu2.push_back(rdiaor[i+j]);
			}
			add_or(cu2);
			cu1.push_back(++cnt);
			add_xor(cu1);
			ans1.push_back(++cnt);
		}
		for(int i = 0; i < h+w-k1-1; ++i){
			vector<int> cu1, cu2;
			for(int j = 0; j <= k1; ++j){
				cu1.push_back(ldiaxor[i+j]);
				cu2.push_back(ldiaor[i+j]);
			}
			add_or(cu2);
			cu1.push_back(++cnt);
			add_xor(cu1);
			ans2.push_back(++cnt);
		}
		add_or(ans1);
		add_or(ans2);
		add_and({cnt+1,cnt+2});
		cnt+=3;
	};
	if(k == 1){
		f(k);
	}
	else{
		f(k);
		int cu = cnt;
		f(k-1);
		add_xor({cu,cnt});
	}
}

• 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