Cod sursa(job #543565)

Utilizator indestructiblecont de teste indestructible Data 28 februarie 2011 12:11:15
Problema Walls Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
//cat de mult trebuie oare sa scrii ca sa se considere ca e ceva nou?!
/*
	Luceafarul de Mihai Eminescu
	A fost oata ca-n povesti,
	A fost ca niciodata
	Din rude mari imparatesti
	O preafrumoasa fata
*/
#include <stdio.h>
#include <algorithm>
#define NMAX 2005
using namespace std;
struct pereche{int a,b;};
int n,m,H[NMAX],a,b;
pereche A[NMAX],C[NMAX];
int B[NMAX][NMAX],D[NMAX],r;
void read()
{
	scanf("%d",&n);
	int i,l=0,x,y;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d",&x,&y);
		A[i].a=l; A[i].b=l+x;
		H[i]=y;
		l+=x+1;
	}
	scanf("%d",&m);
	for (i=1; i<=m; i++)
		scanf("%d%d",&C[i].a,&C[i].b);
}
int cbin(int val)
{
	int i,step;
	for (step=1; step<=r; step<<=1);
	for (i=0; step; step>>=1)
		if (i+step<=r && D[i+step]<=val)
			i+=step;
	return i;
}
void normalizare()
{
	int i,poz=1;
	for (i=1; i<=m; i++)
		D[++r]=C[i].b;
	sort(D+1,D+r+1);
	for (i=2; i<=r; i++)
		if (D[i]!=D[i-1])
			D[++poz]=D[i];
	r=poz;
	for (i=1; i<=m; i++)
		C[i].b=cbin(C[i].b);
}
void solve()
{
	int i,j,hit;
	for (i=1; i<=m; i++)
	{
		hit=0;
		a=C[i].a; b=D[C[i].b];
		for (j=n; j>=1; j--)
			if (a>A[j].a && H[j]>=b)
			{
				hit=1;
				printf("HIT %d %d ",A[j].b-B[j][C[i].b],j);
				B[j][C[i].b]++;
				if (B[j][C[i].b]==A[j].b-A[j].a)
				{
					printf("YES\n");
					H[j]=b-1;
				}
				else
					printf("NO\n");
				break ;
			}
		if (!hit)
			printf("MISS\n");
	}
}
int main()
{
	freopen("walls.in","r",stdin);
	freopen("walls.out","w",stdout);
	read();
	normalizare();
	solve();
	return 0;
}