Submission #1049557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049557		gaurezzz	Vision Program (IOI19_vision)	C++17	100 / 100	13 ms	3368 KiB

vision

#include <bits/stdc++.h>
#include "vision.h"

#define F first 
#define S second
#define ll long long
#define nd '\n'

using namespace std;

ll n,m,k;
ll casillas[205][205];
ll columns[205];
ll grupos[205][10];
ll binario1[10];

ll rows[205];
ll grupos2[205][10];
ll binario2[10];

int binario3 [10];
//el siguiente proceso se hace primero para columnas y luego para filas

    //Armar las columnas
    //or de los elementos de cada columna

    //Agrupar las columnas por indice y por potencia de 2
    //es decir q vamos a ir uniendo con and cada uno de los segmentos
    //si un segmento tiene and como verdadero, significa q la segunda casilla esta ahi

    //Armar los grupos de cada indice vs sus posibilidades por cada potencia
    //entonces abra q usar and para comprobar que ahi esta la segunda casilla

    //entonces con esto vamos a tener en binario la diferencia de distancias

//cuando ya tengamos en binario las dos diferencias entonces hacemos la suma binaria y ya

void diccionario(){

	ll x=0;

	for (ll i=0; i<n; i++){

		for (ll k=0; k<m; k++){

			casillas[i][k] = x;
			x++;
		}
	}

	//cout << "Imprimiendo diccionario" << nd;

	//for (ll i=0; i<n; i++){

	//	for (ll k=0; k<m; k++) //cout << casillas[i][k] << " ";
		//cout << nd;
	//}
}

void armar_columnas(){

	for (ll k=0; k<m; k++){

		vector <int> armando (n,0);

		for (ll i=0; i<n; i++){
			armando[i] = casillas[i][k];
		}

		columns[k] = add_or(armando);

		//cout << "Armando " << k << nd;

		//for (ll i=0; i<n; i++) //cout << armando[i] << " ";

		//cout << nd;
	}

	//cout << "indices columnas" << nd;

	//for (ll i=0; i<m; i++){

		//cout << columns[i] << " ";
	//} //cout << nd;

	for (ll k=0; k<m; k++){

		ll exp=0;

		for (ll pot=1; pot<m; pot*=2, ++exp){

			vector <int> armando;


			for (ll rec=0; rec<pot; rec++){

				if (rec+k >= m) break;
				armando.push_back(columns[rec+k]);
			}

			//cout << "indice: " << k << nd;
			//cout << "potencia: " << pot << nd;

			//for (ll i=0; i<(ll)armando.size(); i++) //cout << armando[i] << ' ';
			//cout << nd;

			grupos[k][exp] = add_or(armando);
		}
	}

	//cout << "grupos" << nd;

	//for (ll i=0; i<m; i++){

		//for (ll k=0; k<10; k++) //cout << grupos[i][k] << " ";
		//cout << nd;
	//}
}
// or d etodas las posibilidades por indice
// and y luego la casilla de todas las posibilidades
// or de todos los and

void armar_binario1(){

	ll exp=0;

	for (ll pot=1; pot<m; pot*=2, ++exp){

		//cout << "pot " << pot << nd;

		vector <int> columnspos;

		for (ll c1=0; c1<m; c1++){

			vector <int> armando;

			ll c2=c1+pot;

			for (; c2 < m; c2+=pot*2){

				if (grupos[c2][exp] != 0) armando.push_back(grupos[c2][exp]);
			}

			//cout << "Armando" << nd;

			//for (ll i=0; i<(ll)armando.size(); i++) //cout << armando[i] << " ";
			//cout << nd;

			if (armando.empty()) break;

			ll casilla = add_or(armando);
			columnspos.push_back(add_and({(int)columns[c1], (int)casilla}));
		}

		binario1[exp] = add_or(columnspos);

		//cout << "columnspos "<< nd;

		//for (ll i=0; i<(ll)columnspos.size(); i++) //cout << columnspos[i] << " ";
		//cout << nd;

		//cout << "binario 1 "<< nd;

		//for (ll i=0; i<10; i++) //cout << binario1[i] << " ";
		//cout << nd;
	}
}

void armar_filas(){

	for (ll k=0; k<n; k++){

		vector <int> armando (m,0);

		for (ll i=0; i<m; i++){
			armando[i] = casillas[k][i];
		}

		rows[k] = add_or(armando);

		//cout << "Armando " << k << nd;

		//for (ll i=0; i<m; i++) //cout << armando[i] << " ";

		//cout << nd;
	}

	//cout << "indices filas" << nd;

	//for (ll i=0; i<n; i++){

		//cout << rows[i] << " ";
	//} //cout << nd;

	for (ll k=0; k<n; k++){

		ll exp=0;

		for (ll pot=1; pot<n; pot*=2, ++exp){

			vector <int> armando;


			for (ll rec=0; rec<pot; rec++){

				if (rec+k >= n) break;
				armando.push_back(rows[rec+k]);
			}

			//cout << "indice: " << k << nd;
			//cout << "potencia: " << pot << nd;

			//for (ll i=0; i<(int)armando.size(); i++) //cout << armando[i] << ' ';
			//cout << nd;

			grupos2[k][exp] = add_or(armando);
		}
	}

	//cout << "grupos" << nd;

	//for (ll i=0; i<m; i++){

	//	for (ll k=0; k<10; k++) //cout << grupos2[i][k] << " ";
		//cout << nd;
	//}
}

void armar_binario2(){

	ll exp=0;

	for (ll pot=1; pot<n; pot*=2, ++exp){

		vector <int> filaspos;

		for (ll c1=0; c1<n; c1++){

			vector <int> armando;

			ll c2=c1+pot;

			for (; c2 < n; c2+=pot*2){

				if (grupos2[c2][exp] != 0) armando.push_back(grupos2[c2][exp]);
			}

			//cout << "Armando" << nd;

			//for (ll i=0; i<(ll)armando.size(); i++) //cout << armando[i] << " ";
			//cout << nd;

			if (armando.empty()) break;

			ll casilla = add_or(armando);
			filaspos.push_back(add_and({(int)rows[c1], (int)casilla}));
		}

		binario2[exp] = add_or(filaspos);

		//cout << "filaspos "<< nd;

		//for (ll i=0; i<(ll)filaspos.size(); i++) //cout << filaspos[i] << " ";
		//cout << nd;

		//cout << "binario 2 "<< nd;

		//for (ll i=0; i<10; i++) //cout << binario2[i] << " ";
		//cout << nd;
	}
}

void columnas(){

	armar_columnas();
	armar_binario1();

}

void filas(){

	armar_filas();
	armar_binario2();

}

void sumar (){

	int operaciones[9];
	int ant;

	ant=0;

	//for (int i=0; i<10; i++) //cout << binario1[i] << " ";
	//cout << nd;

	//for (int i=0; i<10; i++) //cout << binario2[i] << " ";
	//cout << nd;

	int cero = add_and({add_not(0), 0});
	if (binario1[0] == 0) binario1[0] = cero;
	if (binario2[0] == 0) binario2[0] = cero;

	operaciones[4] = add_or({(int)binario1[0], (int)binario2[0]});
	operaciones[5] = add_and({(int)binario1[0], (int)binario2[0]});
	operaciones[6] = add_not(operaciones[5]);
	binario3[0] = add_and({operaciones[4], operaciones[6]});
	ant = operaciones[5];

	for (ll i=1; i<10; i++){

		if (binario1[i] == 0) binario1[i] = cero;
		if (binario2[i] == 0) binario2[i] = cero;

		operaciones[0] = add_and({ant, (int)binario1[i]});
		operaciones[1] = add_or({ant, (int)binario1[i]});
		operaciones[2] = add_not(operaciones[0]);
		operaciones[3] = add_and({operaciones[1], operaciones[2]});
		operaciones[4] = add_or({operaciones[3], (int)binario2[i]});
		operaciones[5] = add_and({operaciones[3], (int)binario2[i]});
		operaciones[6] = add_not(operaciones[5]);
		binario3[i] = add_and({operaciones[4], operaciones[6]});
		ant = add_or({operaciones[0],operaciones[5]});
	}
}

void comparar(){

	int aux = add_not(0);
	int uno = add_or({0,aux});

	bitset<10> kBinario (k);

	vector <int> r(10);

	for (int i=0; i<10; i++){

		if (kBinario[i]){

			r[i] = add_and({binario3[i], uno});
		}

		else{

			r[i] = add_not({binario3[i]});
		}
		
	}

	add_and(r);
}


void construct_network(int H, int W, int K) {

	n=H, m=W, k=K;

	diccionario();

	columnas();
	filas();

	sumar();

	comparar();
}

• 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