Pagini recente » Cod sursa (job #2019442) | Cod sursa (job #335932) | Cod sursa (job #351432) | Cod sursa (job #2743451) | Cod sursa (job #552271)
Cod sursa(job #552271)
#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;
}