Cod sursa(job #1565653)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 11 ianuarie 2016 09:21:55
Problema Zota & Chidil Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.22 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define dim 8192
using namespace std;
int step_count,trap_count,poz=0;
char buff[dim];
vector<pair<int,int> > traps,inverted_traps;
int modul(int x){
    if(x<0)
        return -x;
    return x;
}
void read_integer(int &numar){
    int sign=1;
    numar=0;
    while((buff[poz]<'0'||buff[poz]>'9')&&buff[poz]!='-'){
        poz++;
        if(poz==dim){
            fread(buff,1,dim,stdin);
            poz=0;
        }
    }
    if(buff[poz]=='-'){
        sign=-1;
        poz++;
        if(poz==dim){
            fread(buff,1,dim,stdin);
            poz=0;
        }
    }
    while(buff[poz]>='0'&&buff[poz]<='9'){
        numar=numar*10+buff[poz]-'0';
        poz++;
        if(poz==dim){
            fread(buff,1,dim,stdin);
            poz=0;
        }
    }
    numar*=sign;
}
void read_character(char &character){
    while(buff[poz]!='N'&&buff[poz]!='E'&&buff[poz]!='S'&&buff[poz]!='V'){
        poz++;
        if(poz==dim){
            fread(buff,1,dim,stdin);
            poz=0;
        }
    }
    character=buff[poz];
    poz++;
    if(poz==dim){
        fread(buff,1,dim,stdin);
        poz=0;
    }
}
int main(){
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);
    int x,y,i,dx,dy,step,distance,answer=0;
    char enter,direction;
    fread(buff,1,dim,stdin);
    read_integer(trap_count);
    read_integer(step_count);
    for(i=1;i<=trap_count;i++){
        read_integer(x);
        read_integer(y);
        for(dx=-2;dx<=2;dx++)
            for(dy=-2;dy<=2;dy++)
                if(modul(dx)+modul(dy)<=2&&(x+dx!=0||y+dy!=0))
                    traps.push_back(make_pair(x+dx,y+dy));
    }
    sort(traps.begin(),traps.end());
    trap_count=0;
    for(i=1;i<traps.size();i++)
        if(traps[i]!=traps[i-1]){
            trap_count++;
            traps[trap_count]=traps[i];
        }
    traps.resize(trap_count+1);
    inverted_traps.resize(trap_count+1);
    for(i=0;i<trap_count;i++)
        inverted_traps.push_back(make_pair(traps[i].second,traps[i].first));
    sort(inverted_traps.begin(),inverted_traps.end());
    x=y=0;
    for(step=1;step<=step_count;step++){
        read_character(direction);
        read_integer(distance);
        if(direction=='N'){
            answer=answer+upper_bound(traps.begin(),traps.end(),make_pair(x,y+distance))-lower_bound(traps.begin(),traps.end(),make_pair(x,y+1));
            y+=distance;
        }
        if(direction=='S'){
            answer=answer+upper_bound(traps.begin(),traps.end(),make_pair(x,y-1))-lower_bound(traps.begin(),traps.end(),make_pair(x,y-distance));
            y-=distance;
        }
        if(direction=='E'){
            answer=answer+upper_bound(inverted_traps.begin(),inverted_traps.end(),make_pair(y,x+distance))-lower_bound(inverted_traps.begin(),inverted_traps.end(),make_pair(y,x+1));
            x+=distance;
        }
        if(direction=='V'){
            answer=answer+upper_bound(inverted_traps.begin(),inverted_traps.end(),make_pair(y,x-1))-lower_bound(inverted_traps.begin(),inverted_traps.end(),make_pair(y,x-distance));
            x-=distance;
        }
    }
    printf("%d",answer);
    return 0;
}