Cod sursa(job #552271)

Utilizator maritimCristian Lambru maritim Data 11 martie 2011 23:29:36
Problema Walls Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include<stdio.h>
#include<malloc.h>

#define omie 100005

using namespace std;

typedef struct _nod
{
	long int info;
	long long w;
	struct _nod *adr;
} nod;

typedef struct
{
	int st;
	long long w;
	long long h;
	struct _nod *adr;
} wall;

wall A[200000];
long int n;
long int m;

long int search(int nr,int li,int ls) //cautare binara pentru intervale
{
	if(li<ls)
	{
	if(nr>=A[(li+ls)/2].st && nr<A[(li+ls)/2+1].st) //se verifica
		return (li+ls)/2;
	else if(nr>=A[(li+ls)/2-1].st && nr<A[(li+ls)/2+1].st) //daca face parte dintr-un anumit interval
		return (li+ls)/2-1;
	else if(A[(li+ls)/2].st>nr)
		return search(nr,li,((li+ls)/2)-1);
	else if(A[(li+ls)/2].st<nr)
		return search(nr,((li+ls)/2)+1,ls);
	}
	return (li+ls)/2;
}

int prel(int X,int H,long int *rez,long int *col)
{
	long int po = search(X,1,n); //se cauta elementul cu coordonata corespunzatoare
	while(H>A[po].h && po) po--; //se cauta elementul cu inaltimea corespunzatoare
	*rez = po;
	if(po) //daca s-a gasit vreun element
	{
	  nod *q = A[po].adr;
	  while(q && q->info != H) q = q->adr; //se verefica daca s-a ciuriut pe nivelul dorit
		  if(!q)  //daca nu s-a ciuruit se insemneaza
		  {
			nod *nou = (nod*)malloc(sizeof(nod));
			nou->w = A[po].w - 1;
			nou->info = H;
			nou->adr = A[po].adr;
			A[po].adr = nou;
			*col = A[po].st + nou->w;
			q = A[po].adr;
	      }
		  else //daca s-a ciuruit se micsoreaza grosimea pe nivelul respectiv
		  {
			q->w --;
			*col = A[po].st + q->w;
		  }
		  if(!(q->w)) //daca s-a ciuruit tot nivelul, cade tot de de-asupra
		  {
			A[po].h = H-1;
			return 3;
		  }
		  else //altfel ramane doar c.
		    return 2;
	}
	else //daca nu s-a gasit un element cu inaltimea dorita inseamna ca s-a ratat
	    return 1; //se intoarce "MISS"
}

void citire(void)
{
	long long a;
	long long b;
	long int po;
	long int po2;
	long int rasp;
	FILE *f = fopen("walls.in","r");
	FILE *g = fopen("walls.out","w");
	
	fscanf(f,"%d ",&n);
	A[1].st = 1;
	for(int i=1;i<=n;i++)
	{
	    fscanf(f,"%lld %lld",&A[i].w,&A[i].h);
		A[i+1].st = A[i].st + A[i].w + 1;
	}
	fscanf(f,"%d",&m);
	for(int i=1;i<=m;i++)
	{
		fscanf(f,"%lld %lld",&a,&b);
		rasp = prel(a,b,&po,&po2);
		if(rasp == 1)
			fprintf(g,"MISS\n");
		else if(rasp == 2)
			fprintf(g,"HIT %d %d NO\n",po2,po);
		else if(rasp == 3)
			fprintf(g,"HIT %d %d YES\n",po2,po);
	}
		
	fclose(f);
	fclose(g);
}

int main()
{
	citire();
//	printf("%d ",search(9,1,n));
	return 0;
}