Submission #1066985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066985		jamjanek	Vision Program (IOI19_vision)	C++14	100 / 100	19 ms	3556 KiB

vision

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

vector<int>skosy1[1010],skosy2[1010];
int n, m, k;
int zamien(int a,int b){
	return a*m+b;
}
int zamien2(int typ, int ktore){
	return n*m+2+typ*(n+m-1)+ktore;
}
void construct_network(int N, int M, int K) {
	n = N, m = M, k = K;
	add_not(0);
	add_and({0,n*m});
	// [n*2+1] 0

	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++){
			skosy1[i+j].push_back(zamien(i,j));
			skosy2[-i+j+(n-1)].push_back(zamien(i,j));
		}

	//skosy 1 [S, S+ n+m-1)
	//skosy 2 [S + n+m-1, S+ 2*(n+m)-2)
	for(i=0;i<n+m-1;i++)
		add_or(skosy1[i]);
	for(i=0;i<n+m-1;i++)
		add_or(skosy2[i]);

	// [S+2*(n+m)-2, S+3*(n+m)-3) czy na sufixie od i po skosy1
	// [S+3*(n+m)-3, S+4*(n+m)-4) czy na sufixie od i po skosy2
	
	vector<int>pom;
	for(i=n+m-2;i>=0;i--)
		pom.push_back(zamien2(0,i));
	for(i=0;i<n+m-1;i++){
//		if(i==n+m-2)printf(" %d %d\n", pom.size(), pom[0]);
		add_or(pom);
		pom.pop_back();
	}
	for(i=n+m-2;i>=0;i--)
		pom.push_back(zamien2(1,i));
	for(i=0;i<n+m-1;i++){
		add_or(pom);
		pom.pop_back();
	}
	
	// [S+4*(n+m)-4, S+5*(n+m)-5) czy w odleglosci k na prawo od i po skosy1
	// [S+5*(n+m)-5, S+6*(n+m)-6) czy w odleglosci k na prawo od i po skosy2
	
	for(i=0;i<n+m-1;i++){
		if(i+k<n+m-1)pom = {zamien2(0,i),zamien2(0,i+k)};
		else pom = {n*m+1};
		add_and(pom);
	}
	for(i=0;i<n+m-1;i++){
		if(i+k<n+m-1)pom = {zamien2(1,i),zamien2(1,i+k)};
		else pom = {n*m+1};
		add_and(pom);
	}

	// [S+6*(n+m)-6, S+7*(n+m)-7) czy m odleglosci>= k+1 na prawo od i po skosy1
	// [S+7*(n+m)-7, S+8*(n+m)-8) czy m odleglosci>= k+1 na prawo od i po skosy2
	
	for(i=0;i<n+m-1;i++){
		if(i+k+1<n+m-1)pom = {zamien2(0,i),zamien2(2,i+k+1)};
		else pom = {n*m+1};
		add_and(pom);
	}
	for(i=0;i<n+m-1;i++){
		if(i+k+1<n+m-1)pom = {zamien2(1,i),zamien2(3,i+k+1)};
		else pom = {n*m+1};
		add_and(pom);
	}
	pom.clear();
	for(i=0;i<n+m-1;i++)pom.push_back(zamien2(4,i));
	for(i=0;i<n+m-1;i++)pom.push_back(zamien2(5,i));
	int czy = add_or(pom);

	pom.clear();
	for(i=0;i<n+m-1;i++)pom.push_back(zamien2(6,i));
	for(i=0;i<n+m-1;i++)pom.push_back(zamien2(7,i));
	int czy_not = add_or(pom);

	int not_czy_not = add_not(czy_not);
	add_and({czy,not_czy_not});
}

• 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