Submission #792869

#	Time	Username	Problem	Language	Result	Execution time	Memory
792869		esomer	Vision Program (IOI19_vision)	C++17	0 / 100	7 ms	1052 KiB

vision

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

using namespace std;

#define endl "\n"

typedef long long ll;

int h, w;

void calc(int n, vector<int>& dist, int k, bool type){
	vector<int> val(n); //Whether each row has at least one black.
	for(int i = 0; i < n; i++){
		vector<int> nws;
		if(type == 0){
			for(int j = 0; j < w; j++){
				nws.push_back(i * w + j);
			}
		}else{
			for(int j = 0; j < h; j++){
				nws.push_back(j * w + i);
			}
		}
		val[i] = add_or(nws);
	}
	vector<int> before;
	for(int d = (int)dist.size() - 1; d > 0; d--){
		vector<int> all_res;
		for(int i = 0; i < d && i + d < n; i++){
			vector<int> nws;
			for(int j = i; j < n; j += d){
				nws.push_back(val[j]);
			}
			int orr = add_or(nws);
			int xorr = add_xor(nws);
			int nott = add_not(xorr);
			all_res.push_back(add_and({orr, nott}));
		}
		int orr = add_or(all_res);
		if((int)before.size() == 0){
			before.push_back(orr);
			dist[d] = orr;
			continue;
		}
		int orr_before = add_or(before);
		//Now, I'm one if and(orr, not(orr_before)) is 1, so I'm one and no one before is one).
		int nott = add_not(orr_before);
		dist[d] = add_and({orr, nott});
		before.push_back(dist[d]);
	}
	if((int)before.size() > 0){
		int ind = add_or(before);
		dist[0] = add_not(ind); //If or of all others is 0.	
	}else{
		dist[0] = val[0];
	}
}

void construct_network(int H, int W, int K){
	//Now, I want to get the value of each row.
	h = H;
	w = W;
	vector<int> distr(min(H, K+1), 0);
	vector<int> distc(min(W, K+1), 0);
	calc(H, distr, K, 0);
	calc(W, distc, K, 1);
	vector<int> possibilities;
	for(int i = 0; i < (int)distr.size(); i++){
		int j = K - i;
		if(j >= (int)distc.size()) continue;
		possibilities.push_back(add_and({distr[i], distc[j]}));
	}
	add_or(possibilities);
}

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