Submission #290574

#	Time	Username	Problem	Language	Result	Execution time	Memory
290574		dvdg6566	Vision Program (IOI19_vision)	C++14	100 / 100	64 ms	5652 KiB

vision

#include "vision.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
const int MAXN=400;
const ll MOD=998244353;

vi A;
int H,W,K;
int leftsing[MAXN];
int rightsing[MAXN];
int leftdoub[MAXN];
int rightdoub[MAXN];
int cnt;

ll ins_and(vi A){
	add_and(A);
	return cnt++;
}

ll ins_xor(vi A){
	add_xor(A);
	return cnt++;
}

ll ins_or(vi A){
	add_or(A);
	return cnt++;
}

ll ins_not(ll x){
	add_not(x);
	return cnt++;
}

int check_side(int k,int f){
	vi A;
	for(int sum=0;sum<=H+W-2;++sum){
		if(f)A.pb(leftdoub[sum]);
		else A.pb(rightdoub[sum]);
		vi B;
		int endp=sum+k;
		if(endp > H+W-2)continue;
		for(int t=sum;t<=endp;++t){
			if(f)B.pb(leftsing[t]);
			else B.pb(rightsing[t]);
		}
		// for you to have two things, OR is 1 and XOR is 0
		int a=ins_or(B);
		int b=ins_xor(B);
		int c=ins_not(b);
		vi C;
		C.pb(a);C.pb(c);
		int d=ins_and(C);
		A.pb(d);
	}
	return ins_or(A);
}

int check(int k){
	int a=check_side(k,0);
	int b=check_side(k,1);
	// cerr<<"Distance "<<k<<' '<<a<<' '<<b<<'\n';
	vi A;
	A.pb(a);A.pb(b);
	return ins_and(A);
}

void construct_network(int h, int w, int k) {
	H=h;W=w;K=k;
	cnt=H*W;
	for(int sum=0;sum<=H+W-2;++sum){
		vi A;
		for(int i=0;i<H;++i){
			int w=sum-i;
			if(w<0||w>=W)continue;
			A.pb(i*W+w);
		}
		leftsing[sum]=ins_or(A);

		int a=ins_xor(A);
		int b=ins_not(a);

		vi X;
		X.pb(leftsing[sum]);
		X.pb(b);
		leftdoub[sum]=ins_and(X);
		// cerr<<leftsing[sum]<<' '<<leftdoub[sum]<<'\n';
	}
	for(int dif=0;dif<=H+W-2;++dif){
		vi A;
		// cerr<<"dif "<<dif<<'\n';
		for(int i=0;i<H;++i){
			int j=i+W-dif-1;
			if(j<0||j>=W)continue;
			A.pb(i*W+j);
			// cerr<<i<<' '<<j<<'\n';	
		}
		rightsing[dif]=ins_or(A);

		int a=ins_xor(A);
		int b=ins_not(a);

		vi X;
		X.pb(rightsing[dif]);
		X.pb(b);
		rightdoub[dif]=ins_and(X);
	}
	int a=check(K);
	int b=check(K-1);
	int c=ins_not(b);
	// cerr<<"D "<<a<<' '<<b<<'\n';
	vi C;
	C.pb(a);C.pb(c);
	ins_and(C);
	// cerr<<cnt<<'\n';
}

• 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