Submission #826974

#	Time	Username	Problem	Language	Result	Execution time	Memory
826974		Amylopectin	Vision Program (IOI19_vision)	C++14	100 / 100	11 ms	1644 KiB

vision

#include "vision.h"
#include <vector>
#include <stdio.h>
#include <iostream>
using namespace std;
const int mxn = 2e3 + 10;
int n,m,ta[2][mxn] = {},z[2] = {},ru,nu[2][3][mxn] = {},l[2] = {},se[mxn] = {}
,fta[2][2][mxn] = {},fnu[mxn] = {};
vector<int> fa,fa2[mxn] = {};
int fii(int cl,int cr,int no,int ot,int v,int be,int dep)
{
	if(cl == cr)
	{
		// se[no] = fta[ot][v][cl];
		return 0;
	}
	int mid = (cl+cr) / 2,nbe,nf,nfb,sle;
	add_not(fta[ot][v][mid]);
	nf = ru;
	ru ++;
	add_and({nf,be});
	nfb = ru;
	ru ++;
	add_and({fta[ot][v][mid],be});
	sle = ru;
	ru ++;
	fa2[dep].push_back(nfb);
	fii(cl,mid,no*2,ot,v,sle,dep-1);
	fii(mid+1,cr,no*2+1,ot,v,nfb,dep-1);
	return 0;
}
void construct_network(int H, int W, int K) 
{
	int i,j,cn,cm,fn,fm,k,lava,cxr,nm,ncxr,be,t1,t2,t3,t4;
	n = H;
	m = W;
	lava = K;
	ru = n*m;
	l[0] = n;
	l[1] = m;
	nm = 256;
	add_xor({0,0});
	z[0] = ru;
	ru ++;
	add_not(z[0]);
	z[1] = ru;
	ru++;
	for(i=0; i<n; i++)
	{
		fa.clear();
		for(j=0; j<m; j++)
		{
			fa.push_back(i*m + j);
		}
		add_or(fa);
		ta[0][i] = ru;
		ru ++;
	}
	for(i=n; i<nm; i++)
	{
		ta[0][i] = z[0];
	}
	for(j=0; j<m; j++)
	{
		fa.clear();
		for(i=0; i<n; i++)
		{
			fa.push_back(i*m + j);
		}
		add_or(fa);
		ta[1][j] = ru;
		ru ++;
	}
	for(i=m; i<nm; i++)
	{
		ta[1][i] = z[0];
	}
	// printf("sec1\n");
	for(i=0; i<2; i++)
	{
		for(j=0; j<2; j++)
		{
			if(j == 0)
			{
				fta[i][j][0] = ta[i][0];
				for(k=1; k<nm; k++)
				{
					add_or({fta[i][j][k-1],ta[i][k]});
					fta[i][j][k] = ru;
					ru ++;
				}
			}
			else 
			{
				cxr = ta[i][0];
				fta[i][j][0] = z[0];
				for(k=1; k<nm; k++)
				{
					add_xor({cxr,ta[i][k]});
					cxr = ru;
					ru ++;
					add_not(cxr);
					ncxr = ru;
					ru ++;
					add_and({fta[i][0][k],ncxr});
					fta[i][j][k] = ru;
					ru ++;
				}
			}
			add_not(z[0]);
			add_not(z[0]);
			add_not(z[0]);
			add_not(z[0]);
			add_not(z[0]);
			ru += 5;
			for(k=0; k<8; k++)
			{
				fa2[k].clear();
			}
			fii(0,nm-1,1,i,j,z[1],7);
			for(k=7; k>=0; k--)
			{
				add_or(fa2[k]);
				nu[i][j][k] = ru;
				ru ++;
			}
		}
		//minus
		be = z[0];
		for(j=0; j<8; j++)
		{
			add_xor({be,nu[i][0][j],nu[i][1][j]});
			nu[i][2][j] = ru;
			ru ++;
			add_and({nu[i][0][j],be});
			t1 = ru;
			ru ++;
			add_or({nu[i][0][j],be});
			t2 = ru;
			ru ++;
			add_not(nu[i][1][j]);
			t3 = ru;
			ru ++;
			add_and({t3,t2});
			t4 = ru;
			ru ++;
			add_or({t4,t1});
			be = ru;
			ru ++;
		}

		fa.clear();
		for(j=0; j<nm; j++)
		{
			fa.push_back(ta[i][j]);
		}
		add_xor(fa);
		cxr = ru;
		ru ++;
		add_not(cxr);
		ncxr = ru;
		ru++;
		for(j=0; j<8; j++)
		{
			add_and({ncxr,nu[i][2][j]});
			nu[i][2][j] = ru;
			ru++;
		}
	}
	//add
	be = z[0];
		for(j=0; j<8; j++)
		{
			add_xor({be,nu[0][2][j],nu[1][2][j]});
			fnu[j] = ru;
			ru ++;
			add_or({nu[0][2][j],be});
			t1 = ru;
			ru ++;
			add_or({nu[1][2][j],be});
			t2 = ru;
			ru ++;
			add_or({nu[0][2][j],nu[1][2][j]});
			t3 = ru;
			ru ++;
			add_and({t1,t2,t3});
			be = ru;
			ru ++;
		}
	fnu[8] = be;
	fa.clear();
	for(i=0; i<9; i++)
	{
		if((1<<i) & lava)
		{
			add_xor({z[1],fnu[i]});
		}
		else 
		{
			add_xor({z[0],fnu[i]});
		}
		fa.push_back(ru);
		ru ++;
	}
	add_or(fa);
	add_not(ru);
	ru += 2;
	return ;
	// 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);
}

Compilation message (stderr)

vision.cpp: In function 'int fii(int, int, int, int, int, int, int)':
vision.cpp:17:24: warning: unused variable 'nbe' [-Wunused-variable]
   17 |  int mid = (cl+cr) / 2,nbe,nf,nfb,sle;
      |                        ^~~
vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:34:10: warning: unused variable 'cn' [-Wunused-variable]
   34 |  int i,j,cn,cm,fn,fm,k,lava,cxr,nm,ncxr,be,t1,t2,t3,t4;
      |          ^~
vision.cpp:34:13: warning: unused variable 'cm' [-Wunused-variable]
   34 |  int i,j,cn,cm,fn,fm,k,lava,cxr,nm,ncxr,be,t1,t2,t3,t4;
      |             ^~
vision.cpp:34:16: warning: unused variable 'fn' [-Wunused-variable]
   34 |  int i,j,cn,cm,fn,fm,k,lava,cxr,nm,ncxr,be,t1,t2,t3,t4;
      |                ^~
vision.cpp:34:19: warning: unused variable 'fm' [-Wunused-variable]
   34 |  int i,j,cn,cm,fn,fm,k,lava,cxr,nm,ncxr,be,t1,t2,t3,t4;
      |                   ^~

• 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