Topcoder Birds (CC 2002 REG Semi 500 pointer)

Birds.cpp

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <functional>
#include <set>
#include <numeric>

#define vec vector
#define vint vector<int>
#define vstr vector<string>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define str string
#define stref string&
#define cstref const string&

#define sz(x) int(x.size())
#define beg(x) begin(x)
#define all(x) begin(x), end(x)
#define var auto
#define pbeg(x) &x[0]
#define pend(x) (&x[0] + sz(x))

#define FOR_EVERY_UNIQUE_PAIR(I, J, N) for(int I = 0; I < N; ++I) for(int J = I+1; J < N; ++J) 
#define FOR(I,N) for(int I = 0; I < N; ++I)
#define FORV(I,V) for(int I = 0; I < V.size(); ++I)
#define LOOP(I, J, K) for(int I = J; I < K; ++I)

#define IDX(IT, CONT) distance(begin(CONT), IT)
#define DUMP(X) do {for(auto x:X) cout << x "\t"; cout << endl;} while(0)
#define P(X) cout << X << "\t"
#define NL cout << endl

#define ACCUM accumulate
#define XFORM transform
#define PAR_SUM partial_sum
#define ADJ_DIFF adjacent_difference
#define IN_PROD inner_product

using namespace std;

vstr split(cstref s, str seps=" ")
{
    vstr ret;
    for(var ps = pbeg(s), pd = ps, pe = ps + sz(s); ps < pe; ps = pd + 1)
    {
        ret.eb(str(ps, pd = find_first_of(ps, pe, all(seps))));
    }
    return ret;
}

const int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int days_acc[13] = {0};

struct Move
{ 
    int x, y, d;
    Move(cstref s)
    {
        auto v = split(s, ",");
        x = stoi(v[0]);
        y = stoi(v[1]);
        d = days_acc[stoi(v[2])] + stoi(v[3]);
    }
    
    bool operator<(const Move &other) const
    {
        return d < other.d;
    }
};

class Birds
{
    deque<Move> moves;
    int n;
    
    int far(int i, int j)
    {
        int xx = moves[i].x - moves[j].x, yy = moves[i].y - moves[j].y; 
        return (sqrt(xx * xx + yy * yy)) >= 1000;
    }
    
    int timediff(int later, int earlier)
    {
        return ((moves[later].d - moves[earlier].d) + 365) % 365;
    }
    
    int stay(int idx, int idx2)
    {
        int stay1 = 0;
        for(int i = idx; i < n-1 && far(idx2, i); ++i)
        {
            stay1 += timediff(i+1, i);
            if(far(i, i+1)) break;
        }
        return stay1;
    }    
    
    
public:
    int isMigratory(vector <string> p)
    {
        partial_sum(days, days+12, days_acc+1);
        
        for(auto &s:p) moves.eb(Move(s));
        
        sort(all(moves));
        moves.pb(moves.back());
        moves.back().d=366;
        n = sz(moves);
        
        vec<pair<int, int>> fars; 
        FOR_EVERY_UNIQUE_PAIR(i, j, n) if(far(i,j)) fars.pb(mp(i,j));
        
        for(const auto &p:fars) if(stay(p.first, p.second) >= 90 && stay(p.second, p.first) >= 90) return 1; 
        
        return 0;
    }	
};