Cod sursa(job #541826)

Utilizator laurionLaurentiu Ion laurion Data 25 februarie 2011 14:42:23
Problema Walls Scor 20
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 1 Marime 1.7 kb
#include<cstdio>
#include<vector>

using namespace std;
#define MOD 7
struct _wall
{
	int w,h,poz;
	
	vector<pair<int,int> > G;

} wall[100000];

inline vector<pair<int,int> >::iterator find_value(int x,int y,int& i)
	{

		vector<pair<int,int> >::iterator it;

		for (it = wall[i].G.begin(); it != wall[i].G.end(); ++it)
			if ((*it).first == x && (*it).second==y)
				return it;
	
		return wall[i].G.end();
	}
	
	inline void insert_value(int x,int y,int& i)
	{
        
		//if (find_value(x,y,i) == wall[i].G.end())
			wall[i].G.push_back(make_pair(x,y));
	}



int main()
{
	freopen("walls.in","r",stdin);
	freopen("walls.out","w",stdout);
	
	
	int n,m;
	
	scanf("%d",&n);
	int poz=0;
	for(int i=0;i<n;++i)
	{
		scanf("%d %d",&(wall[i].w),&(wall[i].h));
		wall[i].poz=poz+i+1;
		poz+=wall[i].w;
	}
	
	int x,y;
	for(scanf("%d",&m);m;--m)
	{
		int i;
		for(scanf("%d %d",&x,&y);x>0;--x)
			for( i=n-1;i>=0;--i)
			{
				int j;
				for(j=wall[i].poz+wall[i].w-1;j>=wall[i].poz;--j)
					if(x==j && y<=wall[i].h )
						break;
				if(	j>=wall[i].poz  )
				{
					//if(find_value(wall[i].poz+wall[i].w-1,wall[i].h,i) == wall[i].G.end())
					if (find_value(x,y,i) == wall[i].G.end())
					{
						insert_value(x,y,i);
						goto labelA;
					}
				}		
			}
		labelA:
		if(i<0)
			puts("MISS");
		else
		{
			int j,nr=0;
			printf("HIT %d %d ",x,i+1);
			for(j=wall[i].poz;j<wall[i].poz+wall[i].w;++j)
				if(find_value(j,y,i)!=wall[i].G.end())
					nr++;
			if(nr==wall[i].w)
			{
				printf("YES\n");
				wall[i].h=y-1;
			}
			else
				printf("NO\n");
			
		}
		
	}
	
	
	
	return 0;
}

 //   printf("%d\n", find_value(x) != G[x % MOD].end());