Page 2 of 2

Re: 10043 - Chainsaw Massacre WA???

Posted: Thu May 08, 2014 7:32 pm
by brianfry713
Post or PM me your code.

Re: 10043 - Chainsaw Massacre WA???

Posted: Thu May 08, 2014 9:23 pm
by brianfry713
Input:

Code: Select all

10
2467 1797
1 1655 600
2 1369 902 -371 -54
0
6761 7844
1 3629 7342
4 1561 1617 1629 -187
1 3600 1964
0
8070 5291
2 7858 1035 -7816 4093
4 4702 3963 -686 -1178
2 5149 4020 -670 -2093
1 6877 3645
1 4383 3482
0
1138 4404
1 34 4353
1 475 91
1 76 1370
2 185 4365 -93 -2003
0
4244 7766
1 3548 6481
1 1143 5753
1 2510 6603
0
5803 4766
1 1083 3895
1 5078 3172
1 5636 2070
1 3540 1074
1 3593 716
1 842 593
1 667 915
1 1101 4000
1 5475 2805
0
7614 1737
1 572 1376
1 5919 96
1 4733 890
1 1436 843
2 6946 320 -6281 851
1 4892 74
1 6549 400
1 32 341
0
14 9164
1 9 852
2 11 166 -8 8978
1 9 8938
0
8687 9526
1 8048 7674
1 2410 8977
1 514 8977
1 7828 4370
0
2059 5858
1 1626 3632
1 34 909
0
AC output:

Code: Select all

2207965
36360658
15986256
4470604
24415732
14683084
5885803
113204
70271956
9325936

Re: 10043 - Chainsaw Massacre WA???

Posted: Thu May 08, 2014 11:38 pm
by mack_attack
Thanks, very much got it Accepting now.

It was a combination of reading in the paddock sizes like the puzzle says length then width,
but it would appear the data actually passes width (x) then length (y) and not having a endl after my final puzzle.

I did try swapping those around in previous submissions and adding/removing the final endl but must have change both as same time, causing it to be wrong each time.

That test data is very useful.

Thanks again.

Chainsaw Massacre RE??

Posted: Mon Mar 02, 2015 9:21 pm
by Higros
Help me please, i have compiled and test it in my computer and it works, but I am getting runtime error for a reason i don't know.

Code: Select all

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>

#define MAX 1000
#define MAXSC 10000
using namespace std;
bool acabar = true;


void clean(bool **location, bool *vert, int solVect[1000][5], int sol){
	for(int y = 0; y<sol; y++){
		if(solVect[y][4]==false) continue;
		if(solVect[y][3]-solVect[y][1]==1) continue;
		else {
			int f=solVect[y][1]+1; bool trovat = false;
			while(!trovat && f<solVect[y][3]){
				if(vert[f]){
					int f2=solVect[y][0]+1; bool trovat2 = false;
					while(!trovat2 && f2<solVect[y][2]){
						if(location[f2][f]){
							trovat2=true;
							trovat=true;
							solVect[y][4]=false;
							
						}
						f2++;
					}
					
				}
				f++;
			}
			
		}
		
	}
	
}

int area(int solucion[4]){
	
	int altura = solucion[3]-solucion[1];
	int base = solucion[2]-solucion[0];
	return base*altura;
	
}

int main( int argc, char *argv[] ){
    
    const int location_num = 10000;
    //posiciones de arboles    
    bool **location_matrix;
    
	int numCasos;
    //largo y ancho del campo    
    int l,w;
    //soluciones temporales para el algoritmo    
    int solVect[1000][5];
	int solTemp = 0;
    //numero de soluciones temporales    
    int solac = 0;
    
	//arboles que hay en el escenario actual
	int arb[1000][2];
	int cont = 0;
	
	//vectores para saber si hay algun arbol en su fila o columna
	bool *vertical;
	bool *horitzontal;
    char * linia;
    //posiciones y cantidad de arboles
    int arboles, posX, posY, dX, dY;
    
    scanf( "%d", &numCasos );
    int solFi[numCasos];
	int cantidad = numCasos;
	
	//Cota superior
	int max = 0;
	
	//datos para el algoritmo
	bool salida = false; bool intermedio = false; bool sal = false;
	int derecha = l, izquierda = 0;
	int superior = 20000;
	int baux=0;

	//area calculada
	int a=0;

	//vector con una solucion
	int s_t[4];

    while( --numCasos >= 0 ){
		//cota superior actual
		max=0;
		scanf( "%d %d", &l, &w );
        //printf("%d %d ",l,w);
		vertical = (bool *)malloc((w+1)*sizeof(bool));
        if (!vertical)
        {
                cout<<"error 1 allocating vertical" << endl;
                return 0;
        }
		for (int j=0; j<=w; j++)
                        vertical[j] = false;
		horitzontal = (bool *)malloc((l+1)*sizeof(bool));
        if (!horitzontal)
        {
                cout<<"error 1 allocating horitzontal" << endl;
                return 0;
        }
		for (int j=0; j<=l; j++)
                        horitzontal[j] = false;
		location_matrix = (bool **)malloc((l+1)*sizeof(bool *));
        if (!location_matrix)
        {
                cout<<"error 1 allocating location_matrix" << endl;
                return 0;
        }
        for (int i=0; i<l+1; i++)
        {
                location_matrix[i] = (bool *) malloc((w+1)*sizeof(bool ));
                if (!location_matrix[i])
                {
                        cout<<"error 2 allocating location_matrix" << endl;
                        return 0;
                }
                for (int j=0; j<w+1; j++)
                        location_matrix[i][j] = false;
        }
		
        //for(int i = 0;i<l;i++)for(int j=0;j<w;j++)location_matrix[i][j]=false;
		
        while(arboles!=0 || acabar==1){
		acabar=false;
		scanf( "%d", &arboles );
		//printf("arboles:%d ",arboles);
		if(arboles!=0){
            if(arboles==1){
                scanf( " %d %d", &posX, &posY );
                location_matrix[posX][posY]=true;
				vertical[posY]=true;
				horitzontal[posX]=true;
				arb[cont][0]=posX;
				arb[cont][1]=posY;
				cont++;
            } else {
                scanf( " %d %d %d %d", &posX, &posY, &dX, &dY );
				//printf("posicion1: %d %d posicion2: %d %d ",posX + dX*1-1,posY + dY*1-1,posX + dX*2-1,posY + dY*2-1);
                for(int p =0;p<arboles;p++){
					location_matrix[posX + dX*p][posY + dY*p]=true;
				//printf("posicion1: %d %d posicion2: %d %d ",posX + dX*0,posY + dY*0,posX + dX*1,posY + dY*1);
				vertical[posY + dY*p]=true;
				horitzontal[posX + dX*p]=true;
				arb[cont][0]=posX + dX*p;
				arb[cont][1]=posY + dY*p;
				cont++;
				}
            
			
            
			}
        }
		}
		acabar=true;
       /* for(int n = 0;n<=l;n++){
			printf("\n");
			for(int t=0;t<=w;t++)printf("%d",location_matrix[n][t]);
			}*/
       // printf("\n\n");
		//aqui va el algoritmo
		//para cada arbol del escenario
		for(int j = 0; j<cont; j++){
			//limpiamos la basura
			//clean(location_matrix, vertical, solVect, solTemp);
			salida = false; intermedio = false;
			derecha = l; izquierda = 0;
			superior = 20000;
			baux=0;
			//parte de arriba
			if(arb[j][1]!=0){
				for(int b1=arb[j][1]-1;!salida && b1>=0;b1--){
					switch(intermedio)
					{
						case false:
								  //solucion inmediata
									if(vertical[b1] || b1==0){
										s_t[0] = 0;
										s_t[1] = b1;
										s_t[2] = l;
										s_t[3] = arb[j][1];
										a = area(s_t);
										if(a>max){
											//insertar solucion
											solVect[solTemp][0] = 0;
											solVect[solTemp][1] = b1;
											solVect[solTemp][2] = l;
											solVect[solTemp][3] = arb[j][1];
											solVect[solTemp][4] = true;
											solTemp++;
											//actualizar cota
											max=a;
											
										}
										intermedio = true;
										baux=b1;
										if(location_matrix[arb[j][0]][b1] || b1==0) salida = true;
									}
									break;
						case true:
									//solucion con bordes
									if(location_matrix[arb[j][0]][b1]){
											superior = b1;
											b1=-1;
									}
									if(b1==0) superior=0;
									break;
						
					}
					
					//if(b1==0 && area()>max){ solVect[solTemp]={0,0,};solTemp++;continue;}
				}
				//derecha
				sal = false;
				if(salida==true) sal=true;
				if(arb[j][0]!=l){
					
				
				for(int b2=arb[j][0]+1;!sal && b2<=l;b2++){
					if(horitzontal[b2]){
						for(int temR=baux;temR>superior && !sal;temR--){
						if(location_matrix[b2][temR]) {
							sal = true;
							derecha=b2;
						}
						}
					}
					
				}
				} else{
					derecha=l;
				}
				//if(sal) salida = false;
				//izquierda
				if(arb[j][0]!=0){
				for(int b3=arb[j][0]-1;!salida && b3>=0;b3--){
					if(horitzontal[b3]){
						for(int temR2=baux;temR2>superior && !salida;temR2--){
							if(location_matrix[b3][temR2]) {
								salida=true; 
								izquierda=b3;
							}
						}
					
					}
				
				}
				} else{
					izquierda=0;
				}
				if(superior!=20000){
					//insertar solucion con superior izquierda y derecha mas el arbol como limites
					s_t[0] = izquierda;
					s_t[1] = superior;
					s_t[2] = derecha;
					s_t[3] = arb[j][1];
					a = area(s_t);
					if(a>max){
						//insertar solucion
						solVect[solTemp][0] = izquierda;
						solVect[solTemp][1] = superior;
						solVect[solTemp][2] = derecha;
						solVect[solTemp][3] = arb[j][1];
						solVect[solTemp][4] = true;
						solTemp++;
						//actualizar cota
						max=a;
						
					}
				}
			}
			//vamos con la derecha
			salida = false; intermedio = false;
			derecha = w; izquierda = 0;
			superior = 20000;
			baux=0;
			if(arb[j][0]!=l){
				for(int b1=arb[j][0]+1;!salida && b1<=l;b1++){
					switch(intermedio)
					{
						case false:
								  //solucion inmediata
									if(horitzontal[b1] || b1==l){
									s_t[0] = arb[j][0];
									s_t[1] = 0;
									s_t[2] = b1;
									s_t[3] = w;
									a = area(s_t);
									if(a>max){
										//insertar solucion
										solVect[solTemp][0] = arb[j][0];
										solVect[solTemp][1] = 0;
										solVect[solTemp][2] = b1;
										solVect[solTemp][3] = w;
										solVect[solTemp][4] = true;
										solTemp++;
										//actualizar cota
										max=a;
										
									}
										intermedio = true;
										baux=b1;
										if(location_matrix[b1][arb[j][1]] || b1==l) salida = true;
									}
									break;
						case true:
									//solucion con bordes
									if(location_matrix[b1][arb[j][1]]){
											superior = b1;
											b1=l+1;
									}
									if(b1==l) superior=l;
									break;
						
					}
					
					//if(b1==0 && area()>max){ solVect[solTemp]={0,0,};solTemp++;continue;}
				}
				//derecha
				sal = false;
				if(salida==true) sal=true;
				if(arb[j][1]!=w){
					
				
				for(int b2=arb[j][1]+1;!sal && b2<=w;b2++){
					if(vertical[b2]){
						for(int temR=baux;temR<superior && !sal;temR++){
						if(location_matrix[temR][b2]) {
							sal = true;
							derecha=b2;
						}
						}
					}
					
				}
				} else{
					derecha=w;
				}
				//if(sal) salida = false;
				//izquierda
				if(arb[j][1]!=0){
				for(int b3=arb[j][1]-1;!salida && b3<=0;b3--){
					if(horitzontal[b3]){
						for(int temR2=baux;temR2<superior && !salida;temR2++){
							if(location_matrix[temR2][b3]) {
								salida=true; 
								izquierda=b3;
							}
						}
					
					}
				
				}
				} else{
					izquierda=0;
				}
				if(superior!=20000){
					//insertar solucion con superior izquierda y derecha mas el arbol como limites
					s_t[0] = arb[j][0];
					s_t[1] = izquierda;
					s_t[2] = superior;
					s_t[3] = derecha;
					a = area(s_t);
					if(a>max){
						//insertar solucion
						solVect[solTemp][0] = arb[j][0];
						solVect[solTemp][1] = izquierda;
						solVect[solTemp][2] = superior;
						solVect[solTemp][3] = derecha;
						solVect[solTemp][4] = true;
						solTemp++;
						//actualizar cota
						max=a;
						
					}
				}
			}
			
			//vamos con la parte de debajo
			salida = false; intermedio = false;
			derecha = 0; izquierda = l;
			superior = 20000;
			baux=0;
			if(arb[j][1]!=w){
				for(int b1=arb[j][1]+1;!salida && b1<=w;b1++){
					switch(intermedio)
					{
						case false:
								  //solucion inmediata
									if(vertical[b1] || b1==w){
									s_t[0] = 0;
									s_t[1] = arb[j][1];
									s_t[2] = l;
									s_t[3] = b1;
									a = area(s_t);
									if(a>max){
										//insertar solucion
										solVect[solTemp][0] = 0;
										solVect[solTemp][1] = arb[j][1];
										solVect[solTemp][2] = l;
										solVect[solTemp][3] = b1;
										solVect[solTemp][4] = true;
										solTemp++;
										//actualizar cota
										max=a;
										
									}
										intermedio = true;
										baux=b1;
										if(location_matrix[arb[j][0]][b1] || b1==w) salida = true;
									}
									break;
						case true:
									//solucion con bordes
									if(location_matrix[arb[j][0]][b1]){
											superior = b1;
											b1=w+1;
									}
									if(b1==w) superior=w;
									break;
						
					}
					
					//if(b1==0 && area()>max){ solVect[solTemp]={0,0,};solTemp++;continue;}
				}
				//derecha
				sal = false;
				if(salida==true) sal=true;
				if(arb[j][0]!=0){
					
				
				for(int b2=arb[j][0]-1;!sal && b2>=0;b2--){
					if(horitzontal[b2]){
						for(int temR=baux;temR<superior && !sal;temR++){
						if(location_matrix[b2][temR]) {
							sal = true;
							derecha=b2;
						}
						}
					}
					
				}
				} else{
					derecha=0;
				}
				//if(sal) salida = false;
				//izquierda
				if(arb[j][0]!=l){
				for(int b3=arb[j][0]+1;!salida && b3<=l;b3++){
					if(horitzontal[b3]){
						for(int temR2=baux;temR2<superior && !salida;temR2++){
							if(location_matrix[b3][temR2]) {
								salida=true; 
								izquierda=b3;
							}
						}
					
					}
				
				}
				} else{
					izquierda=l;
				}
				if(superior!=20000){
					//insertar solucion con superior izquierda y derecha mas el arbol como limites
					s_t[0] = derecha;
					s_t[1] = arb[j][1];
					s_t[2] = izquierda;
					s_t[3] = superior;
					a = area(s_t);
					if(a>max){
						//insertar solucion
						solVect[solTemp][0] = derecha;
						solVect[solTemp][1] = arb[j][1];
						solVect[solTemp][2] = izquierda;
						solVect[solTemp][3] = superior;
						solVect[solTemp][4] = true;
						solTemp++;
						//actualizar cota
						max=a;
						
					}
				}
			}
			//vamos con la izquierda
			salida = false; intermedio = false;
			derecha = 0; izquierda = w;
			superior = 20000;
			baux=0;
			if(arb[j][0]!=0){
				for(int b1=arb[j][0]-1;!salida && b1>=0;b1--){
					switch(intermedio)
					{
						case false:
								  //solucion inmediata
									if(horitzontal[b1] || b1==0){
									s_t[0] = b1;
									s_t[1] = 0;
									s_t[2] = arb[j][0];
									s_t[3] = w;
									a = area(s_t);
									if(a>max){
										//insertar solucion
										solVect[solTemp][0] = b1;
										solVect[solTemp][1] = 0;
										solVect[solTemp][2] = arb[j][0];
										solVect[solTemp][3] = w;
										solVect[solTemp][4] = true;
										solTemp++;
										//actualizar cota
										max=a;
										
									}
										intermedio = true;
										baux=b1;
										if(location_matrix[b1][arb[j][1]] || b1==0) salida = true;
									}
									break;
						case true:
									//solucion con bordes
									if(location_matrix[b1][arb[j][1]]){
											superior = b1;
											b1=-1;
									}
									if(b1==0) superior=0;
									break;
						
					}
					
					//if(b1==0 && area()>max){ solVect[solTemp]={0,0,};solTemp++;continue;}
				}
				//derecha
				sal = false;
				if(salida==true) sal=true;
				if(arb[j][1]!=0){
					
				
				for(int b2=arb[j][1]-1;!sal && b2>=0;b2--){
					if(vertical[b2]){
						for(int temR=baux;temR>superior && !sal;temR--){
						if(location_matrix[temR][b2]) {
							sal = true;
							derecha=b2;
						}
						}
					}
					
				}
				} else{
					derecha=0;
				}
				//if(sal) salida = false;
				//izquierda
				if(arb[j][1]!=w){
				for(int b3=arb[j][1]+1;!salida && b3<=w;b3++){
					if(vertical[b3]){
						for(int temR2=baux;temR2>superior && !salida;temR2--){
							if(location_matrix[temR2][b3]) {
								salida=true; 
								izquierda=b3;
							}
						}
					
					}
				
				}
				} else{
					izquierda=w;
				}
				if(superior!=20000){
					//insertar solucion con superior izquierda y derecha mas el arbol como limites
					s_t[0] = superior;
					s_t[1] = derecha;
					s_t[2] = arb[j][0];
					s_t[3] = izquierda;
					a = area(s_t);
					if(a>max){
						//insertar solucion
						solVect[solTemp][0] = superior;
						solVect[solTemp][1] = derecha;
						solVect[solTemp][2] = arb[j][0];
						solVect[solTemp][3] = izquierda;
						solVect[solTemp][4] = true;
						solTemp++;
						//actualizar cota
						max=a;
						
					}
				}
			}
			
			
		}//fin del arbol actual
		
		if(max!=0)solFi[numCasos]=max; else solFi[numCasos]=l*w;
		free(location_matrix);
		free(vertical);
		free(horitzontal);
    }//fin del caso actual
	//mostramos por pantalla el resultado
	for(int nu = cantidad-1;nu>-1;nu--){
		
	
	printf("%d\n",solFi[nu]);
	
	}
	return 0;
}//fin del main