Cod sursa(job #1730704)

Utilizator GoogalAbabei Daniel Googal Data 17 iulie 2016 15:00:18
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include<fstream>
#include<algorithm>

using namespace std;

#define MAXCELL 1400000

typedef struct
{
    int x, y;
} cell;

int N, M, i, j, x, y, k, nr_cells, t1, t2, res;
char c;
pair < int, int > v1[ MAXCELL ], v2[ MAXCELL ];

inline int search(pair < int, int > v[ MAXCELL ], int x, int y)
{
    int st = 1, end = nr_cells, mid;
    pair < int, int > t;
    t.first = x, t.second = y;

    if(v[nr_cells] <= t)
        return nr_cells+1;
    while(st < end)
    {
        mid = (st+end)/2;
        if(v[mid] <= t)
            st = mid + 1;
        else end = mid;
    }

    return st;
}

int main()
{
    ifstream f("zc.in");
    ofstream g("zc.out");

    f >> N >> M;
    for(i = 1; i <= N; ++i)
    {
        f >> x >> y;
        for(t1 = -2; t1 <= 2; ++t1)
            for(t2 = -2; t2 <= 2; ++t2)
                if(abs(t1) + abs(t2) <= 2 && (x + t1 != 0 || y + t2 != 0) )
                    ++nr_cells, v1[nr_cells].first = x + t1, v1[nr_cells].second = y + t2;;
    }
    v1[0].first = v1[1].first - 1;
    sort(v1+1, v1+nr_cells+1);
    for(i = 1; i <= nr_cells; ++i)
        if(v1[i].first != v1[i-1].first || v1[i].second != v1[i-1].second)
            ++k, v1[k] = v1[i];
    nr_cells = k;
    for(i = 1; i <= nr_cells; ++i)
        v2[i].first = v1[i].second, v2[i].second = v1[i].first;
    sort(v2+1, v2+nr_cells+1);

    x = y = 0;
    for(i = 1; i <= M; ++i)
    {
        f >> c >> k;
        switch(c)
        {
            case 'N':
            {
                t1 = search(v1, x, y);
                y += k;
                t2 = search(v1, x, y);
            } break;
            case 'S':
            {
                t2 = search(v1, x, y-1);
                y -= k;
                t1 = search(v1, x, y-1);
            } break;
            case 'V':
            {
                t2 = search(v2, y, x-1);
                x -= k;
                t1 = search(v2, y, x-1);
            } break;
            case 'E':
            {
                t1 = search(v2, y, x);
                x += k;
                t2 = search(v2, y, x);
            } break;
        }
        res += t2 - t1;
    }

    g << res << '\n';

    f.close();
    g.close();

    return 0;
}