Submission #799064

#	Time	Username	Problem	Language	Result	Execution time	Memory
799064		esomer	Vision Program (IOI19_vision)	C++17	100 / 100	91 ms	10568 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> previous((int)dist.size());
	dist[0] = add_xor(val);
	vector<int> all_others = {dist[0]};
	int org = n;
	if(n > 160){
		for(int i = 160; i < n; i++){
			vector<int> possibilities;
			for(int j = 0; j + i < n; j++){
				possibilities.push_back(add_and({val[j], val[j+i]}));
			}
			dist[i] = add_or(possibilities);
			all_others.push_back(dist[i]);
		}
		n = 160;
	}
	int orr1 = add_or(all_others);
	for(int q = 2; q < n; q++){
		bool prime = 1;
		for(int k = 2; k * k <= q; k++){
			if((q % k) == 0){
				prime = 0;
			}
		}
		if(prime){
			vector<int> powers = {q};
			int x = q * q;
			while(x < n){
				powers.push_back(x);
				x *= q;
			}
			int before = orr1;
			vector<vector<int>> all_res((int)powers.size());
			for(int i = 0; i < org; i++){
				vector<bool> done(org, 0);
				int lst = -1;
				for(int l = 0; l < (int)powers.size(); l++){
					if(i + powers[l] >= org || i >= powers[l]) continue;
					vector<int> nws;
					for(int j = 0; j < org; j++){
						if(j % powers[l] != i && done[j] == 0){
							done[j] = 1;
							nws.push_back(val[j]);
						}
					}
					int orr;
					if(lst == -1){
						orr = add_or(nws);
					}else{
						nws.push_back(lst);
						orr = add_or(nws);
					}
					lst = orr;
					all_res[l].push_back(orr);
				}
			}
			for(int l = (int)powers.size() - 1; l >= 0; l--){
				int orr = add_not(add_and(all_res[l]));
				int nott = add_not(before);
				previous[powers[l]] = add_and({orr, nott});
				before = add_or({before, previous[powers[l]]});
			}
		}
	}
	int before = orr1;
	for(int d = n - 1; d > 0; d--){
		if(d == 1){
			//It's only 1 if it is not any of the previous.
			int nott = add_not(before);
			dist[d] = add_and({nott, add_not(dist[0])});
			continue;
		}
		vector<int> all_res;
		int x = d;
		for(int k = 2; k * k <= x; k++){
			ll crr = 1;
			while(x % k == 0){
				crr *= k;
				x /= k;
			}
			if(crr != 1){
				all_res.push_back(previous[crr]);
			}
		}
		if(x > 1){
			all_res.push_back(previous[x]);
		}
		int orr = add_and(all_res);
		//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(before);
		dist[d] = add_and({orr, nott});
		before = add_or({before, dist[d]});
	}
}

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(H, 0);
	vector<int> distc(W, 0);
	calc(H, distr, K, 0);
	calc(W, distc, K, 1);
	vector<int> possibilities;
	for(int i = 0; i < (int)distr.size() && i <= K; 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: 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