Submission #612711

#	Time	Username	Problem	Language	Result	Execution time	Memory
612711		definitelynotmee	Vision Program (IOI19_vision)	C++17	100 / 100	27 ms	3388 KiB

vision

#include "vision.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;


void construct_network(int H, int W, int K) {
	int diag = H+W-1;
	matrix<int> prin(diag), sec(diag);
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			prin[i+j].push_back(i*W+j);
			sec[i-j+W-1].push_back(i*W+j);
		}
	}

	// cout << "principal:\n";
	// for(int i = 0; i < prin.size(); i++){
	// 	cout << i << ": ";
	// 	for(int j : prin[i]){
	// 		cout << "(" << j/W << ',' << j%W << ") ";
	// 	}
	// 	cout << '\n';
	// }
	// cout << "secundaria:\n";
	// for(int i = 0; i < sec.size(); i++){
	// 	cout << i << ": ";
	// 	for(int j : sec[i]){
	// 		cout << "(" << j/W << ',' << j%W << ") ";
	// 	}
	// 	cout << '\n';
	// }

	vector<int> ploc(diag), sloc(diag);
	int timer = H*W-1;
	for(int i = 0; i < diag; i++){
		vector<int> qry;
		for(int j : prin[i]){
			qry.push_back(j);
		}
		add_or(qry);
		ploc[i] = ++timer;
	}
	
	for(int i = 0; i < diag; i++){
		vector<int> qry;
		for(int j : sec[i]){
			qry.push_back(j);
		}
		add_or(qry);
		sloc[i] = ++timer;
	}
	
	vector<int> kloc;
	for(int i = 0;i + K < diag; i++){
		vector<int> q1 = {ploc[i],ploc[i+K]}, q2 = {sloc[i],sloc[i+K]};
		kloc.push_back(++timer);
		kloc.push_back(++timer);
		add_and(q1);
		add_and(q2);
	}
	
	vector<int> biggerloc;

	for(int i = 0; i < diag; i++){
		vector<int> q1, q2;
		for(int j = i+K+1; j < diag; j++){
			q1.push_back(ploc[j]);
			q2.push_back(sloc[j]);
		}
		if(q1.size()){
			timer++;
			add_or(q1);
			add_and({timer,ploc[i]});
			biggerloc.push_back(++timer);
		}
		
		if(q2.size()){
			timer++;
			add_or(q2);
			add_and({timer,sloc[i]});
			biggerloc.push_back(++timer);
		}
		
	}
	
	if(biggerloc.size()){
		add_or(biggerloc);
		timer++;
		add_not(timer);
		timer++;
	} else {
		add_or(kloc);
		timer++;
	}
	
	add_or(kloc);
	timer++;
	add_and({timer-1,timer});
}

• 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