Submission #293191

#	Time	Username	Problem	Language	Result	Execution time	Memory
293191		AlanChen	Vision Program (IOI19_vision)	C++14	100 / 100	25 ms	2116 KiB

vision

#include "vision.h"


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

template<class A> using v=vector<A>;
template<class A,class B=A> using p=pair<A,B>;

typedef v<int> vi;
typedef p<int> pi;
typedef string str;

#define f first
#define s second
#define mp make_pair
#define ins insert
#define pb push_back
#define sz(S) (int)S.size()


#define get4(a,b,c,d,...) d

#define lp3(x,a,b) for(int x=(a);x<(b);x++)
#define lp2(x,a) lp3(x,0,a)
#define lp1(a) lp2(loopvar,a)
#define lp(x...) get4(x,lp3,lp2,lp1,0)(x)

#define trv(x,S) for(auto& x:(S))


int c0,c1;
struct num
{
	int x[9];
	num()
	{
		lp(i,9) x[i]=c0;
	}
};
num addnum(num n1,num n2)
{
	num ans;
	int carry=add_and({{n1.x[0],n2.x[0]}});
	ans.x[0]=add_xor({n1.x[0],n2.x[0]});
	lp(i,1,9){
		ans.x[i]=add_xor({carry,n1.x[i],n2.x[i]});
		if(i<8) carry=add_or({
			add_and({n1.x[i],n2.x[i]}),
					add_and({carry,n2.x[i]}),
					add_and({n1.x[i],carry})
		});
	}
	return ans;
}
num cplm(num n1)
{
	num ans;
	lp(i,9) ans.x[i]=add_not(n1.x[i]);

	num n2;
	n2.x[0]=c1;

	return addnum(ans,n2);
}

int n,m,tgt;
int orig[500][500];
int prj[2][500];
int disthelp[2][500][500];
int dist[2][500];
int isx[2][500];
int dim[2];




void construct_network(int H, int W, int Tgt)
{
	n=H,m=W,tgt=Tgt;


	{
		vi Ns;
		lp(i,n*m) {
			Ns.pb(i);
		}
		c1=add_or(Ns);
		c0=add_not(c1);
	}

	lp(i,n) lp(j,m) orig[i][j]=i*m+j;

	lp(i,n)
	{
		vi Ns;
		lp(j,m) Ns.pb(orig[i][j]);
		prj[0][i]=add_or(Ns);
	}
	lp(j,m)
	{
		vi Ns;
		lp(i,n) Ns.pb(orig[i][j]);
		prj[1][j]=add_or(Ns);
	}
	dim[0]=n,dim[1]=m;


	num fds[2];
	lp(d,2)
	{
		int iss;
		{
			vi Ns;
			lp(i,dim[d]) Ns.pb(prj[d][i]);
			iss=add_xor(Ns);
		}
		int isn=add_not(iss);


		int issamebit[8];
		int consenbit[8];
		lp(i,8)
		{
			vi Ns; Ns.pb(c0);
			lp(j,dim[d]) if(bitset<9>(j)[i]) Ns.pb(prj[d][j]);
			issamebit[i]=add_not(add_xor(Ns));
			consenbit[i]=add_or(Ns);
		}
		num possnums[9][2];
		lp(numsame,9)
		{
			lp(i,numsame) lp(j,2) possnums[numsame][j].x[i]=consenbit[i];
			lp(i,numsame,8) lp(j,2){
				vi Ns; Ns.pb(c0);
				lp(alln,dim[d]) if(bitset<9>(alln)[numsame]==j&&bitset<9>(alln)[i]) Ns.pb(prj[d][alln]);
				possnums[numsame][j].x[i]=add_or(Ns);
			}
		}
		num curr[2];
		lp(j,2) curr[j]=possnums[0][j];

		lp(i,1,8) issamebit[i]=add_and({issamebit[i-1],issamebit[i]});

		lp(j,2) lp(ns,1,9) lp(bt,8){
			curr[j].x[bt]=add_or({
				add_and({issamebit[ns-1],possnums[ns][j].x[bt]}),
						add_and({add_not(issamebit[ns-1]),curr[j].x[bt]})
			});
		}
		num diff=addnum(curr[0],cplm(curr[1]));
		num diff2=cplm(diff);
		num fd;
		lp(bt,9) fd.x[bt]=add_or({
			add_and({diff2.x[8],diff.x[bt]}),
					add_and({diff.x[8],diff2.x[bt]})
		});
		lp(bt,9) fd.x[bt]=add_and({isn,fd.x[bt]});
		fds[d]=fd;

	}
	num ttl=addnum(fds[0],fds[1]);

	vi ansarr;

	lp(i,9)
	{
		if(bitset<9>(tgt)[i]) ansarr.pb(ttl.x[i]);
		else ansarr.pb(add_not(ttl.x[i]));
	}

	add_and(ansarr);
}

• 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