Cod sursa(job #868166)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 30 ianuarie 2013 19:04:34
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define M1 66666666
#define M2 671235
#define MOD 666013

#define LE 1666666

#define mp make_pair
#define pb push_back

using namespace std;
ifstream f ( "zc.in" );
ofstream g ( "zc.out" );
int xx[] = {0, 0, 0,  0,   0, 1,  1, 1, -1, -1, -1, -2, 2};
int yy[] = {0, 1, 2, -1, - 2, 0, -1, 1,  0,  1, -1,  0, 0};

inline void PUSH ( int X, int Y );
inline bool FIND ( int X, int Y );
bool comp ( pair<int, int> X, pair<int, int> Y );
inline int  BIN ( int one, int PARAM, int X, int Y );

int n, m, i;
int AA, BB;
pair<int, int> P[2][LE];
char C;
int l, result;
vector<pair<int, int> > H[MOD+666];
int K;
int X, Y;

int main()
{
    f >> n >> m;

    for ( int j = 1; j <= n; ++j )
    {
        f >> AA >> BB;
        swap(BB,AA);

        for ( i = 0; i < 13; ++i )
            if (  FIND ( AA + xx[i], BB + yy[i] ) == false )
            {
                ++K;
                P[0][K] = P[1][K] = mp ( AA + xx[i], BB + yy[i] );
                swap ( P[1][K].first, P[1][K].second );

                PUSH ( AA + xx[i], BB + yy[i] );
            }
    }

    sort ( P[0] + 1, P[0] + K + 1, comp );
    sort ( P[1] + 1, P[1] + K + 1, comp );


    /*for ( i = 1; i <= m; ++i )
    {
        f >> C >> l;

        if ( C == 'N' )
            result += BIN ( 1, Y, X + 1, X + l ), X += l;

        if ( C == 'S' )
            result += BIN ( 1, Y, X - l, X - 1 ), X -= l;

        if ( C == 'E' )
            result += BIN ( 0, X, Y + 1, Y + l ), Y += l;

        if ( C == 'V' )
            result += BIN ( 0, X, Y-l, Y -1 ), Y -= l;
    }

*/
    g << result << '\n';

    f.close();
    g.close();
    return 0;
}

inline void PUSH ( int X, int Y )
{
    X = X < 0 ? -X : X;
    Y = Y < 0 ? -Y : Y;
    int R = ( X % M1 + Y % M2 ) % MOD;
    H[R].pb ( mp ( X, Y ) );
}

inline bool FIND ( int X, int Y )
{
    if ( X == 0 && Y == 0 ) return true;

    X = X < 0 ? -X : X;
    Y = Y < 0 ? -Y : Y;
    int R = ( X % M1 + Y % M2 ) % MOD;
    int N = H[R].size();

    for ( int i = 0; i < N; ++i )
        if ( H[R][i].first == X && H[R][i].second == Y )
            return true;

    return false;
}

bool comp ( pair<int, int>X, pair<int, int>  Y )
{
    if ( X.first == Y.first )
        return X.second < Y.second;

    return X.first < Y.first;
}


inline int  BIN ( int one, int PARAM, int X, int Y )
{
    int pos, step, pos2;

    for ( step = 1; step <= K; step *= 2 );

    for ( pos = 0; step; step /= 2 )
        if ( pos + step <= K && P[one][pos+step].first <= PARAM )
            if ( P[one][pos+step].second < X||P[one][pos+step].first<PARAM )
                pos += step;

    ++pos;
    for ( step = 1; step <= K; step *= 2 );

    for ( pos2 = 0; step; step /= 2 )
        if ( pos2 + step <= K && P[one][pos2+step].first <= PARAM )
            if ( P[one][pos2+step].second <= Y|| P[one][pos2+step].first<PARAM)
                pos2 += step;

    if (P[one][pos].first!=PARAM||P[one][pos2].first!=PARAM)
      return 0;

    if (pos2==0&&pos==0) return 0;
    return pos2 - pos + 1;
}