Cod sursa(job #541855)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 25 februarie 2011 14:52:28
Problema Walls Scor 40
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 1 Marime 1.45 kb
#include<algorithm>
using namespace std;
#include<vector>

#define DIM 100005
#define pb push_back
#define mp make_pair
#define fs first
#define sc second

int n,m,w[4][DIM];
vector <pair <int,int> > a[DIM];

int main ()
{
    freopen("walls.in","r",stdin);
    freopen("walls.out","w",stdout);
    int i,*aux,wall,j,adanc;
    double x,y;
    bool gasit;

    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%d%d\n",&w[1][i],&w[2][i]);
        if(i==1)
            w[3][1]=w[1][1];
        else
            w[3][i]=w[3][i-1]+1+w[1][i];
    }
    scanf("%d",&m);
    for(i=1;i<=m;++i)
    {
        scanf("%lf%lf",&x,&y);
        aux=lower_bound (1+w[3],1+w[3]+n,x);

        wall=int(aux-w[3]-1);
        while(w[2][wall]<y && wall>-1)
            --wall;
        if(wall==-1)
            printf("MISS\n");
        else
        {
            gasit=false;
            adanc=1;
            for(j=0;j<a[wall].size ();++j)
                if(a[wall][j].fs==y)
                {
                    adanc=++a[wall][j].sc;
                    gasit=true;break;
                }
            if(gasit==false)
                a[wall].pb (mp (y,1));
            printf("HIT %d %d ",w[3][wall]-adanc+1,wall);

            if(adanc==w[1][wall])
            {
                w[2][wall]=y-1;
                printf("YES\n");
            }
            else
                printf("NO\n");
        }
    }
    return 0;
}