Submission #1048787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048787		noyancanturk	Vision Program (IOI19_vision)	C++17	8 / 100	23 ms	2908 KiB

vision

#include "vision.h"

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int lim=210;

int pref1[lim],pref2[lim];
int p1(int l,int r){
	if(!l)return pref1[r];
	return add_xor({pref1[r],pref1[l-1]});
}
int p2(int l,int r){
	if(!l)return pref2[r];
	return add_xor({pref2[r],pref2[l-1]});
}

struct {
	int tree[4*lim];
	int P,VAL;
	int N;
	void init(int n){
		N=n;
	}
	void update(int l,int r,int node){
		if(l==r){
			tree[P]=VAL;
			return;
		}
		int mid=(l+r)>>1,child=node<<1;
		if(P<=mid)update(l,mid,child);
		else update(mid+1,r,child|1);
	}
	void update(int p,int val) {
		P=p,VAL=val;
		update(0,N-1,1);
	}
	int build(int l,int r,int node){
		if(l==r){
			return tree[node];
		}
		int mid=(l+r)>>1,child=node<<1;
		return tree[node]=add_or({build(l,mid,child),build(mid+1,r,child|1)});
	}
	void build(){
		build(0,N-1,1);
	}
	vector<int>need;
	int L,R;
	void query(int l,int r,int node){
		if(L<=l&&r<=R){
			need.pb(tree[node]);
			return;
		}
		if(r<L||R<l)return;
		int mid=(l+r)>>1,child=node<<1;
		query(l,mid,child),query(mid+1,r,child|1);
	}
	int query(int l,int r){
		L=l,R=r;
		need.clear();
		query(0,N-1,1);
		return add_or(need);
	}
}st1,st2;


void construct_network(int H, int W, int K) {
	#define tr(x,y) ((x)*W+(y))
	#define check(x,y) (0<=(x)&&(x)<H&&0<=(y)&&(y)<W)
	vector<int>sat1,sat2,sat3;
	int r1[H+W+1],r2[H+W+1];
	for(int i=0;i<H+W+1;i++){
		vector<int>kk,ll;
		for(int x=0;x<H+W+1;x++){
			if(check(x,x+i)){
				kk.pb(tr(x,x+i));
			}
			if(check(x,i-x)){
				ll.pb(tr(x,i-x));
			}
		}
		if(kk.size())r1[i]=add_or(kk);
		else r1[i]=-1;
		if(ll.size())r2[i]=add_or(ll);
		else r2[i]=-1;
	}
	for(int i=0;i+K<H+W+1;i++){
		if(r1[i]!=-1&&r1[i+K]!=-1)
			sat1.pb(add_and({r1[i],r1[i+K]}));
		if(r2[i]!=-1&&r2[i+K]!=-1)
			sat1.pb(add_and({r2[i],r2[i+K]}));
	}
	int xor1[H],or1[H];
	st1.init(H);
	for(int i=0;i<H;i++){
		vector<int>th;
		for(int j=0;j<W;j++){
			th.pb(tr(i,j));
		}
		xor1[i]=add_xor(th);
		if(i)pref1[i]=add_xor({xor1[i],pref1[i-1]});
		else pref1[i]=xor1[i];
		or1[i]=add_or(th);
		st1.update(i,or1[i]);
	}
	int xor2[W],or2[W];
	st2.init(W);
	for(int i=0;i<W;i++){
		vector<int>th;
		for(int j=0;j<H;j++){
			th.pb(tr(j,i));
		}
		xor2[i]=add_xor(th);
		if(i)pref2[i]=add_xor({xor2[i],pref2[i-1]});
		else pref2[i]=xor2[i];
		or2[i]=add_or(th);
		st2.update(i,or2[i]);
	}
	st1.build(),st2.build();
	for(int i=0;i<H;i++){
		int haveblack=st1.query(i,min(i+K,H-1));
		int haveboth=p1(i,min(i+K,H-1));
		sat2.pb(add_and({haveblack,add_not(haveboth)}));
	}
	for(int i=0;i<W;i++){
		int haveblack=st2.query(i,min(i+K,W-1));
		int haveboth=p2(i,min(i+K,W-1));
		sat3.pb(add_and({haveblack,add_not(haveboth)}));
	}
	//ending
	add_and({add_or(sat1),add_or(sat2),add_or(sat3)});
}

/*
void construct_network(int H, int W, int K) {
	std::vector<int> Ns;
	Ns = {0, 1};
	int a = add_and(Ns);
	Ns = {0, a};
	int b = add_or(Ns);
	Ns = {0, 1, b};
	int c = add_xor(Ns);
	add_not(c);
}
*/

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