Acceler8

/*!
 * \file main.cpp
 * \brief This file contains source code that solves the Work Hard - Play Hard problem for the Acceler8 contest
 */
#include <cstdlib>
#include <cstring>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/time.h>
#include <omp.h>

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <iterator>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <istream>
#include <streambuf>

using namespace std;


const double EPS = 1e-9;
const int INT_INF = 2000000000;
const int TYPES = 5;
const float FLOAT_INF = 1e100;

typedef unsigned long ulong;
typedef char* cstr;

struct Flight {
        int id;
        int from;
        int to;
        int company;
        ulong take_off_time;/*!< Take off time (epoch). */
        ulong land_time;/*!< Land time (epoch). */
        float cost;/*!< The cost of the flight. */
        float discount;/*!< The discount applied to the cost. */
};



class File {
        struct membuf: streambuf {
                membuf(cstr begin, cstr end) {
                        this->setg(begin, begin, end);
                }
        };

        cstr filename;
        size_t size;
        int descriptor;
        cstr mapped;
        size_t buffer_size;
        cstr buffer;
        size_t buffer_ptr;
        membuf *sbuf;

public:
        File(cstr filename) :
                filename(filename), buffer_ptr(0) {
        }

        void fopen() {
                descriptor = open(filename, O_RDONLY);
                size = lseek(descriptor, 0, SEEK_END);

                if (size == 0) {
                        mapped = new char[0];
                } else {
                        mapped = (cstr) mmap(0, size, PROT_READ, MAP_SHARED, descriptor, 0);
                        if (mapped == MAP_FAILED) {
                                cerr << "Problem while opening the file " << filename << endl;
                                exit(0);
                        }
                }

                buffer_size = size + 1;
                buffer = new char[buffer_size];
                memset(buffer, 0, buffer_size);
                sbuf = new membuf(mapped, mapped + size);
        }

        membuf* get_mapped_buf() {
                return sbuf;
        }

        void fclose() {
                if (size != 0) {
                        munmap(mapped, size);
                }
                close(descriptor);
                delete sbuf;
        }

        void dispose() {
                delete[] buffer;
        }

        cstr read_line(istream& input) {
                cstr begin = buffer + buffer_ptr;
                input.getline(begin, buffer_size - buffer_ptr);
                buffer_ptr += strlen(begin) + 1;
                return begin;
        }
};


struct Parameters {
        cstr from;/*!< The city where the travel begins */
        cstr to;/*!< The city where the conference takes place */
        ulong dep_time_min;/*!< The minimum departure time for the conference (epoch). No flight towards the conference's city must be scheduled before this time. */
        ulong dep_time_max;/*!< The maximum departure time for the conference (epoch). No flight towards the conference's city must be scheduled after this time.  */
        ulong ar_time_min;/*!< The minimum arrival time after the conference (epoch). No flight from the conference's city must be scheduled before this time.  */
        ulong ar_time_max;/*!< The maximum arrival time after the conference (epoch). No flight from the conference's city must be scheduled after this time.  */
        ulong max_layover_time;/*!< You don't want to wait more than this amount of time at the airport between 2 flights (in seconds) */
        ulong vacation_time_min;/*!< Your minimum vacation time (in seconds). You can't be in a plane during this time. */
        ulong vacation_time_max;/*!< Your maximum vacation time (in seconds). You can't be in a plane during this time. */
        vector<cstr> airports_of_interest;/*!< The list of cities you are interested in. */
        cstr flights_file;/*!< The name of the file containing the flights. */
        cstr alliances_file;/*!< The name of the file containing the company alliances. */
        cstr work_hard_file;/*!< The file used to output the work hard result. */
        cstr play_hard_file;/*!< The file used to output the play hard result. */
        int nb_threads;/*!< The maximum number of worker threads */
};


class cstr_hash {
public:
        long operator()(const cstr &str) const {
                long result = 0;
                cstr a = str;
                while (*a != 0) {
                        result = (result << 8) + result + (*a);
                        ++a;
                }
                return result;
        }
};

class cstr_comparator {
public:
        bool operator()(const cstr &s1, const cstr &s2) const {
                return strcmp(s1, s2) == 0;
        }
};

unordered_set<cstr, cstr_hash, cstr_comparator> string_pool;


typedef pair<float, int> fPair;
typedef pair<double, int> dPair;
typedef vector<vector<fPair> > Graph;
typedef vector<Flight> Travel;
typedef unordered_map<cstr, int> umap;

enum {
        FROM_ANY = 0,
        FROM_THIS = 1,
        FIRST_THIS = 2,
        FROM_ALLIANCE = 3,
        FIRST_ALLIANCE = 4
};

int id_counter = 0;
int city_counter = 0;
int company_counter = 0;

umap id_by_string;
umap city_by_string;
umap company_by_string;

vector<cstr> id_by_index;
vector<cstr> city_by_index;
vector<cstr> company_by_index;

Graph home_vacation_conference_graph;
Graph home_conference_vacation_graph;

vector<int> home_vacation_conference_graph_size;
vector<int> home_conference_vacation_graph_size;

vector<vector<Flight*> > flightsByDepartureCities;
vector<vector<Flight*> > flightsByArrivalCities;

vector<vector<bool> > alliances;





void create_home_vacation_conference_graph(vector<Flight*> &flights, Parameters& parameters);
void create_home_conference_vacation_graph(vector<Flight*> &flights, Parameters& parameters);

void find_home_conference_vacation_path(vector<Flight *> &flights, Parameters& parameters,
                                                                                cstr vacation, vector<dPair > &prev);
void find_home_vacation_conference_path(vector<Flight*> &flights, Parameters& parameters,
                                                                                cstr vacation, vector<dPair > &prev);

time_t convert_to_timestamp(int day, int month, int year, int hour, int minute,
                int seconde);
time_t convert_string_to_timestamp(cstr s);

void read_parameters(Parameters& parameters, int argc, char **argv);

void parse_flight(vector<Flight>& flights, cstr line, Parameters &parameters);
void parse_flights(vector<Flight>& flights, File &flights_file, Parameters &parameters);
void parse_alliance(cstr line);
void parse_alliances(File &alliances_file);

void print_params(Parameters &parameters);
void print_flight(Flight& flight, ofstream&);
void print_alliances(vector<vector<int> > &alliances);
void print_flights(vector<Flight>& flights, ofstream& output);
void print_travel(Travel& travel, ofstream& output);

long get_time();

int add(cstr s, umap &m, int &counter, vector<cstr> &v);
int add_company(cstr s);
int add_city(cstr s);
int add_id(cstr s);
cstr get_from_pool(cstr c);

bool flightByTakeOffComparator(Flight* f1, Flight* f2);
bool flightByArriveComparator(Flight* f1, Flight* f2);
float getCostWithDiscount(Flight *fl, int type);
bool can_fly(Flight* flight, ulong min_time, ulong max_time);

void fill_travel(vector<Flight*> &flights, int finish, int start,
                Travel &result, vector<dPair > &prev, int layersize);
void dijkstra(Graph &graph, int start, int finish, vector<dPair > &prev);
void wire_two_flights(Graph &g, Flight* f1, Flight* f2, int i1, int i2);
void make_graph_layer(vector<Flight*> &flights, ulong min_time, ulong max_time,
                Graph& graph, int layer, int layersize, Parameters & params);
void wire_two_layers(Graph &g, int from, int to, int city, int layersize, ulong l2, ulong r2);



/*
 *      Dijkstra algorithm base on priority queue
 *      Returns result in "prev" parameter which for any vertex will contain
 *      previous vertex in path and distance to in (or -1 if there is no path
 *      to this vertex)
 */
void dijkstra(Graph &graph, int start, int finish, vector<dPair > &prev) {
        vector<double> d(graph.size(), FLOAT_INF);
        prev.resize(graph.size());
        d[start] = 0;

        priority_queue<dPair > q;
        q.push(make_pair(0, start));
        while (!q.empty()) {
                int v = q.top().second;
                if (v == finish) {
                        break;
                }

                double cur_d = -q.top().first;
                q.pop();
                if (cur_d > d[v] + EPS) {
                        continue;
                }

                for (size_t j = 0; j < graph[v].size(); ++j) {
                        int to = graph[v][j].second;
                        double len = graph[v][j].first;

                        if (d[v] + len < d[to]) {
                                d[to] = d[v] + len;
                                prev[to].first = d[v];
                                prev[to].second = v;
                                q.push(make_pair(-d[to], to));
                        }
                }
        }

        #pragma omp parallel for
        for (size_t i = 0; i < graph.size(); ++i) {
                if (d[i] == FLOAT_INF) {
                        prev[i].second = -1;
                }
        }
}

/*
 *      Comparator for sorting flights by take off time
 */
bool flightByTakeOffComparator(Flight* f1, Flight* f2) {
        return f1->take_off_time < f2->take_off_time;
}

/*
 *      Comparator for sorting flights by landing time
 */
bool flightByArriveComparator(Flight* f1, Flight* f2) {
        return f1->land_time < f2->land_time;
}

/*
 *      Calculates flight cost with discount
 */
float getCostWithDiscount(Flight *fl, int type) {
        if (type == 0) {
                return fl->cost;
        } else if (type < 3) {
                return (fl->cost) * 0.7f;
        } else {
                return (fl->cost) * 0.8f;
        }
}


/*
 *      Creates edges between two flights in graph
 */
void wire_two_flights(Graph &g, Flight* f1, Flight* f2, int i1, int i2) {
#define P_B(t) push_back(make_pair(getCostWithDiscount(f2, t), i2 + t))
        if(f1->company == f2->company) {
                g[i1 + FIRST_THIS].P_B(FROM_THIS);
                g[i1 + FROM_THIS].P_B(FROM_THIS);
                g[i1 + FROM_ALLIANCE].P_B(FROM_THIS);
        } else if(alliances[f1->company][f2->company]) {
                g[i1 + FIRST_ALLIANCE].P_B(FROM_ALLIANCE);
                g[i1 + FIRST_ALLIANCE].P_B(FIRST_THIS);
                g[i1 + FROM_ALLIANCE].P_B(FROM_ALLIANCE);
                g[i1 + FROM_ALLIANCE].P_B(FIRST_THIS);
                g[i1 + FROM_THIS].P_B(FROM_ALLIANCE);
                g[i1 + FROM_THIS].P_B(FIRST_THIS);
        } else {
                g[i1 + FROM_ANY].P_B(FROM_ANY);
                g[i1 + FROM_ANY].P_B(FIRST_THIS);
                g[i1 + FROM_ANY].P_B(FIRST_ALLIANCE);
                g[i1 + FROM_ALLIANCE].P_B(FROM_ANY);
                g[i1 + FROM_ALLIANCE].P_B(FIRST_THIS);
                g[i1 + FROM_ALLIANCE].P_B(FIRST_ALLIANCE);
                g[i1 + FROM_THIS].P_B(FROM_ANY);
                g[i1 + FROM_THIS].P_B(FIRST_THIS);
                g[i1 + FROM_THIS].P_B(FIRST_ALLIANCE);
        }
}

/*
 *      Checks if it's possible to use given flight in given time interval
 */
bool can_fly(Flight* flight, ulong min_time, ulong max_time) {
        return flight->take_off_time >= min_time && flight->land_time <= max_time;
}

/*
 *      Creates one graph layer. It will contain all flights which are in given time interval
 */
void make_graph_layer(vector<Flight*> &flights, ulong min_time, ulong max_time,
                Graph& graph, int layer, int layersize, Parameters & params) {

        int prod = layer * layersize;

        for (size_t i = 0; i < flights.size(); ++i) {
                Flight fake;
                Flight * current = flights[i];

                if (!can_fly(current, min_time, max_time)) {
                        continue;
                }

                vector<Flight*> &fromVector = flightsByDepartureCities[current->to];
                ulong time_of_arrival = current->land_time;
                fake.take_off_time = time_of_arrival;
                vector<Flight*>::iterator lb = lower_bound(fromVector.begin(),
                                fromVector.end(), &fake, flightByTakeOffComparator);

                while (lb != fromVector.end() &&
                           (*lb)->take_off_time <= time_of_arrival + params.max_layover_time) {
                        Flight *target = (*lb);
                        if (can_fly(target, min_time, max_time)) {
                                wire_two_flights(graph, current, target,
                                                                 prod + current->id * TYPES,
                                                                 prod + target->id * TYPES);
                        }
                        ++lb;
                }
        }

        int fromId = city_by_string[params.from];

        Flight fake;
        fake.take_off_time = min_time;
        vector<Flight*>::iterator firstFlight = lower_bound(
                                flightsByDepartureCities[fromId].begin(),
                                flightsByDepartureCities[fromId].end(), &fake,
                                flightByTakeOffComparator);
        vector<fPair> &v = graph[(layer + 1) * layersize - 2];

        while (firstFlight != flightsByDepartureCities[fromId].end()
                   && (*firstFlight)->take_off_time <= max_time) {
                if (can_fly(*firstFlight, min_time, max_time)) {
                        for (int toType = 0; toType < 5; toType++) {
                                if (toType == 1 || toType == 3)
                                        continue;
                                v.push_back(make_pair(getCostWithDiscount((*firstFlight), toType),
                                                                          prod + TYPES * (*firstFlight)->id + toType));
                        }
                }
                ++firstFlight;
        }

        fake.land_time = min_time;
        firstFlight = lower_bound(flightsByArrivalCities[fromId].begin(),
                                                          flightsByArrivalCities[fromId].end(),
                                                          &fake, flightByArriveComparator);
        while (firstFlight != flightsByArrivalCities[fromId].end()
                   && (*firstFlight)->land_time <= max_time) {
                if (can_fly(*firstFlight, min_time, max_time)) {
                        for (int fromType = 0; fromType < 5; fromType++) {
                                if (fromType == 2 || fromType == 4)
                                        continue;
                                graph[layersize * layer + TYPES * (*firstFlight)->id + fromType].push_back(
                                                        make_pair(0, (layer + 1) * layersize - 1));
                        }
                }
                ++firstFlight;
        }
}

/*
 *      Connects two graph layers by given city using flights which are in given interval
 */
void wire_two_layers(Graph &g, int from, int to, int city, int layersize, ulong l2, ulong r2) {
        vector<Flight*> &dep = flightsByDepartureCities[city];
        vector<Flight*> &arr = flightsByArrivalCities[city];

        for (size_t i = 0; i < arr.size(); ++i) {
                ulong last_time = INT_INF;
                int index1 = layersize * from + arr[i]->id * TYPES;

                for (size_t j = i + 1; j < arr.size(); ++j) {
                        if (arr[i]->company == arr[j]->company) {
                                int index2 = layersize * from + arr[j]->id * TYPES;
                                for (int ty = 0; ty < TYPES; ++ty) {
                                        g[index1 + ty].push_back(make_pair(0, index2 + ty));
                                }
                                last_time = arr[j]->land_time;
                                break;
                        }
                }

                Flight fake;
                fake.take_off_time = arr[i]->land_time;
                vector<Flight*>::iterator it = lower_bound(dep.begin(), dep.end(),
                                &fake, flightByTakeOffComparator);

                while (it != dep.end()) {
                        int index2 = layersize * to + (*it)->id * TYPES;
                        Flight* flight1 = arr[i];
                        Flight* flight2 = (*it);
                        ulong t1 = flight2->take_off_time;
                        ulong t2 = flight1->land_time;
                        if (t1 > last_time)
                                break;
                        if (t1 > t2 && can_fly(flight2, l2, r2)) {
                                wire_two_flights(g, flight1, flight2, index1, index2);
                        }
                        ++it;
                }
        }
}


/*
 *      Adds string to string pool if there is no such string in pool.
 *      Else returns pointer to equal string in pool
 */
cstr get_from_pool(cstr c) {
        unordered_set<cstr, cstr_hash, cstr_comparator>::iterator it = string_pool.find(c);
        if (it == string_pool.end()) {
                string_pool.insert(c);
                return c;
        } else {
                return *it;
        }
}


/*
 *      Adds company name to companies dictionary
 */
int add_company(cstr s) {
        return add(get_from_pool(s), company_by_string, company_counter,
                        company_by_index);
}

/*
 *      Adds city name to cities dictionary
 */
int add_city(cstr s) {
        return add(get_from_pool(s), city_by_string, city_counter, city_by_index);
}

/*
 *      Adds id string to ids dictionary
 */
int add_id(cstr s) {
        return add(get_from_pool(s), id_by_string, id_counter, id_by_index);
}


/*
 *      Returns current system time in milliseconds
 */
long get_time() {
        timeval time;
        gettimeofday(&time, NULL);
        return (time.tv_sec * 1000) + (time.tv_usec / 1000);
}


/*
 *      Using dijkstra function output creates vector of flights to print.
 */
void fill_travel(vector<Flight*> &flights, int finish, int start,
                Travel &result, vector<dPair > &prev, int layersize) {
        dPair v = prev[finish];
        while (v.second != start) {
                if (!result.empty() && fabs(result.back().discount) < 1e-3) {
                        result.pop_back();
                }
                int index = v.second % layersize / TYPES;
                Flight* f = flights[index];
                result.push_back(*f);
                result.back().discount = (v.first - prev[v.second].first) / result.back().cost;
                v = prev[v.second];
        }
}



/*
 *      Restores initial graph structure
 *      (removes information about vacation city which was added
 *      while solving one of play hard tasks)
 */
void restore_graph(Graph &graph, vector<int> &graph_size) {
        for (size_t i = 0; i < graph.size(); i++) {
                graph[i].resize(graph_size[i]);
        }
}

/*
 *      Solves Work Hard task.
 */
Travel work_hard(vector<Flight*>& flights) {
        int layersize = flights.size() * TYPES + 2;
        int source_vertex = layersize - 2;
        int target_vertex = layersize * 2 - 1;

        // it's possible to use home_conference_vacation_graph as
        // Work Hard graph because we can not to connect the 2nd and the 3rd
        // layers by vacation city
        Graph &g = home_conference_vacation_graph;
        vector<int> &g_size = home_conference_vacation_graph_size;

        restore_graph(g, g_size);

        vector<dPair > prev;
        dijkstra(g, source_vertex, target_vertex, prev);

        // return result if exists
        if (prev[target_vertex].second != -1) {
                Travel result;
                fill_travel(flights, target_vertex, source_vertex, result, prev, layersize);
                reverse(result.begin(), result.end());
                return result;
        } else {
                return Travel();
        }
}


/*
 *      Constructs two graphs:
 *      1. for home->vacation->conference path finding
 *      2. for home->conference->vacation path finding (it can also be used for work hard task)
 */
void create_graphs(vector<Flight*> &flights, Parameters& parameters) {
        #pragma omp parallel sections
        {
                #pragma omp section
                create_home_vacation_conference_graph(flights, parameters);

                #pragma omp section
                create_home_conference_vacation_graph(flights, parameters);
        }
}

/*
 *      Creates graph for home->conference->vacation path finding (it can also be used for work hard task)
 */
void create_home_conference_vacation_graph(vector<Flight*> &flights, Parameters& parameters) {
        int layersize = flights.size() * TYPES + 2;
        Graph &g = home_conference_vacation_graph;
        vector<int> &g_size = home_conference_vacation_graph_size;

        g.resize(layersize * 3);
        g_size.resize(layersize * 3);

        ulong l0 = parameters.dep_time_min;
        ulong r0 = parameters.dep_time_max;
        ulong l1 = parameters.ar_time_min;
        ulong r1 = parameters.ar_time_max;
        ulong l2 = parameters.ar_time_max + parameters.vacation_time_min;
        ulong r2 = parameters.ar_time_max + parameters.vacation_time_max;

        make_graph_layer(flights, l0, r0, g, 0, layersize, parameters);
        make_graph_layer(flights, l1, r1, g, 1, layersize, parameters);
        make_graph_layer(flights, l2, r2, g, 2, layersize, parameters);
        wire_two_layers(g, 0, 1, city_by_string[parameters.to], layersize, l1, r1);

        for (size_t i = 0; i < g.size(); ++i) {
                g_size[i] = g[i].size();
        }
}


/*
 *      Creates graph for home->vacation->conference path finding
 */
void create_home_vacation_conference_graph(vector<Flight*> &flights, Parameters& parameters) {
        int layersize = flights.size() * TYPES + 2;
        Graph &g = home_vacation_conference_graph;
        vector<int> &g_size = home_vacation_conference_graph_size;

        g.resize(layersize * 3);
        g_size.resize(layersize * 3);

        ulong l0 = parameters.dep_time_min - parameters.vacation_time_max;
        ulong r0 = parameters.dep_time_min - parameters.vacation_time_min;
        ulong l1 = parameters.dep_time_min;
        ulong r1 = parameters.dep_time_max;
        ulong l2 = parameters.ar_time_min;
        ulong r2 = parameters.ar_time_max;

        make_graph_layer(flights, l0, r0, g, 0, layersize, parameters);
        make_graph_layer(flights, l1, r1, g, 1, layersize, parameters);
        make_graph_layer(flights, l2, r2, g, 2, layersize, parameters);
        wire_two_layers(g, 1, 2, city_by_string[parameters.to], layersize, l2, r2);

        for (size_t i = 0; i < g.size(); ++i) {
                g_size[i] = g[i].size();
        }
}


/*
 *      Solves "Play Hard" task for one vacation city.
 */
Travel play_hard_for_one(vector<Flight*> &flights, Parameters& parameters, cstr vacation) {
        int layersize = flights.size() * TYPES + 2;
        int source_vertex = layersize - 2;
        int target_vertex = layersize * 3 - 1;

        vector<dPair > prev1;
        find_home_vacation_conference_path(flights, parameters, vacation, prev1);

        vector<dPair > prev2;
        find_home_conference_vacation_path(flights, parameters, vacation, prev2);

        // choosing the best from two ways (if there is)
        if (prev1[target_vertex].second != -1 &&
                        (prev2[target_vertex].second == -1 ||
                         prev1[target_vertex].first < prev2[target_vertex].first)) {
                Travel result;
                fill_travel(flights, target_vertex, source_vertex, result, prev1, layersize);
                reverse(result.begin(), result.end());
                return result;
        } else if (prev2[target_vertex].second != -1) {
                Travel result;
                fill_travel(flights, target_vertex, source_vertex, result, prev2, layersize);
                reverse(result.begin(), result.end());
                return result;
        } else {
                return Travel();
        }
}


void find_home_conference_vacation_path(vector<Flight*> &flights, Parameters& parameters,
                                                                                cstr vacation, vector<dPair > &prev) {
        int layersize = flights.size() * TYPES + 2;
        int source_vertex = layersize - 2;
        int target_vertex = layersize * 3 - 1;

        Graph &g = home_conference_vacation_graph;
        #pragma omp parallel for
        for (size_t i = 0; i < g.size(); ++i) {
                g[i].resize(home_conference_vacation_graph_size[i]);
        }
        ulong l = parameters.ar_time_max + parameters.vacation_time_min;
        ulong r = parameters.ar_time_max + parameters.vacation_time_max;
        wire_two_layers(g, 1, 2, city_by_string[vacation], layersize, l, r);
        dijkstra(g, source_vertex, target_vertex, prev);
}


void find_home_vacation_conference_path(vector<Flight*> &flights, Parameters& parameters,
                                                                                cstr vacation, vector<dPair > &prev) {
        int layersize = flights.size() * TYPES + 2;
        int source_vertex = layersize - 2;
        int target_vertex = layersize * 3 - 1;

        Graph &g = home_vacation_conference_graph;
        #pragma omp parallel for
        for (size_t i = 0; i < g.size(); ++i) {
                g[i].resize(home_vacation_conference_graph_size[i]);
        }
        ulong l = parameters.dep_time_min;
        ulong r = parameters.dep_time_max;
        wire_two_layers(g, 0, 1, city_by_string[vacation], layersize, l, r);
        dijkstra(g, source_vertex, target_vertex, prev);
}


/*
 *      Solves "Play Hard" for all vacation cities and "Work Hard"
 */
vector<Travel> solve_task(vector<Flight*> &flights, Parameters& parameters) {
        vector<Travel> result(parameters.airports_of_interest.size() + 1);
        for (size_t i = 0; i <= parameters.airports_of_interest.size(); i++) {
                if (i == parameters.airports_of_interest.size()) {
                        result[i] = work_hard(flights);
                } else {
                        result[i] = play_hard_for_one(flights, parameters,
                                        parameters.airports_of_interest[i]);
                }
        }

        return result;
}

vector<time_t> tc(100000);
time_t get_time(int year, int month) {
        size_t key = 13 * year + month;

        if(key >= tc.size()){
                tc.resize(key * 2);
        }

        if (tc[key] == 0) {
                tm time;
                time.tm_year = year - 1900;
                time.tm_mon = month - 1;
                time.tm_mday = 0;
                time.tm_hour = time.tm_min = time.tm_sec = 0;
                time_t res = mktime(&time);
                tc[key] = res;
        }

        return tc[key];
}

time_t convert_to_timestamp(int day, int month, int year, int hour, int minute, int seconde) {
        time_t res = get_time(year, month);
        res += (day) * 60 * 60 * 24;
        res += hour * 60 * 60;
        res += minute * 60;
        res += seconde;

        return res;
}

void copy_substr(cstr dst, cstr src, int pos, int len) {
        memcpy(dst, src + pos, len);
        dst[len] = 0;
}

time_t convert_string_to_timestamp(cstr s) {
        if (strlen(s) != 14) {
                cerr << "The given string is not a valid timestamp" << endl;
                exit(0);
        } else {
                char buf[5];
                int day, month, year, hour, minute, seconde;

                copy_substr(buf, s, 2, 2);
                day = atoi(buf);
                copy_substr(buf, s, 0, 2);
                month = atoi(buf);
                copy_substr(buf, s, 4, 4);
                year = atoi(buf);
                copy_substr(buf, s, 8, 2);
                hour = atoi(buf);
                copy_substr(buf, s, 10, 2);
                minute = atoi(buf);
                copy_substr(buf, s, 12, 2);
                seconde = atoi(buf);
                return convert_to_timestamp(day, month, year, hour, minute, seconde);
        }
}

void print_params(Parameters &parameters) {
        cout << "From : " << parameters.from << endl;
        cout << "To : " << parameters.to << endl;
        cout << "dep_time_min : " << parameters.dep_time_min << endl;
        cout << "dep_time_max : " << parameters.dep_time_max << endl;
        cout << "ar_time_min : " << parameters.ar_time_min << endl;
        cout << "ar_time_max : " << parameters.ar_time_max << endl;
        cout << "max_layover_time : " << parameters.max_layover_time << endl;
        cout << "vacation_time_min : " << parameters.vacation_time_min << endl;
        cout << "vacation_time_max : " << parameters.vacation_time_max << endl;
        cout << "flights_file : " << parameters.flights_file << endl;
        cout << "alliances_file : " << parameters.alliances_file << endl;
        cout << "work_hard_file : " << parameters.work_hard_file << endl;
        cout << "play_hard_file : " << parameters.play_hard_file << endl;
        vector<cstr>::iterator it = parameters.airports_of_interest.begin();
        for (; it != parameters.airports_of_interest.end(); it++)
                cout << "airports_of_interest : " << *it << endl;
        cout << "flights : " << parameters.flights_file << endl;
        cout << "alliances : " << parameters.alliances_file << endl;
        cout << "nb_threads : " << parameters.nb_threads << endl;
}

void print_flight(Flight& flight, ofstream& output) {
        struct tm * take_off_t, *land_t;
        take_off_t = gmtime(((const time_t*) &(flight.take_off_time)));
        output << company_by_index[flight.company] << "-";
        output << "" << id_by_index[flight.id] << "-";
        output << city_by_index[flight.from] << " (" << (take_off_t->tm_mon + 1)
                        << "/" << take_off_t->tm_mday << " " << take_off_t->tm_hour << "h"
                        << take_off_t->tm_min << "min" << ")" << "/";
        land_t = gmtime(((const time_t*) &(flight.land_time)));
        output << city_by_index[flight.to] << " (" << (land_t->tm_mon + 1) << "/"
                        << land_t->tm_mday << " " << land_t->tm_hour << "h"
                        << land_t->tm_min << "min" << ")-";
        output << flight.cost << "$" << "-" << flight.discount * 100 << "%" << endl;

}

void read_parameters(Parameters& parameters, int argc, char **argv) {
        for (int i = 0; i < argc; i++) {
                string current_parameter = argv[i];
                if (current_parameter == "-from") {
                        add_city(argv[++i]);
                        parameters.from = get_from_pool(argv[i]);
                } else if (current_parameter == "-arrival_time_min") {
                        parameters.ar_time_min = convert_string_to_timestamp(argv[++i]);
                } else if (current_parameter == "-arrival_time_max") {
                        parameters.ar_time_max = convert_string_to_timestamp(argv[++i]);
                } else if (current_parameter == "-to") {
                        add_city(argv[++i]);
                        parameters.to = get_from_pool(argv[i]);
                } else if (current_parameter == "-departure_time_min") {
                        parameters.dep_time_min = convert_string_to_timestamp(argv[++i]);
                } else if (current_parameter == "-departure_time_max") {
                        parameters.dep_time_max = convert_string_to_timestamp(argv[++i]);
                } else if (current_parameter == "-max_layover") {
                        parameters.max_layover_time = atol(argv[++i]);
                } else if (current_parameter == "-vacation_time_min") {
                        parameters.vacation_time_min = atol(argv[++i]);
                } else if (current_parameter == "-vacation_time_max") {
                        parameters.vacation_time_max = atol(argv[++i]);
                } else if (current_parameter == "-vacation_airports") {
                        while (i + 1 < argc && argv[i + 1][0] != '-') {
                                add_city(argv[++i]);
                                parameters.airports_of_interest.push_back(
                                                get_from_pool(argv[i]));
                        }
                } else if (current_parameter == "-flights") {
                        parameters.flights_file = argv[++i];
                } else if (current_parameter == "-alliances") {
                        parameters.alliances_file = argv[++i];
                } else if (current_parameter == "-work_hard_file") {
                        parameters.work_hard_file = argv[++i];
                } else if (current_parameter == "-play_hard_file") {
                        parameters.play_hard_file = argv[++i];
                } else if (current_parameter == "-nb_threads") {
                        parameters.nb_threads = atoi(argv[++i]);
                }

        }
}

vector<int> pos;
void fill_pos(cstr line) {
        pos.clear();
        pos.push_back(0);
        int len = strlen(line);
        for (int i = 0; i < len; ++i) {
                if (line[i] == ';') {
                        line[i] = 0;
                        pos.push_back(i + 1);
                }
        }
}

bool interval_inside(ulong i1l, ulong i1r, ulong i2l, ulong i2r) {
        return i1l >= i2l && i1r <= i2r;
}

bool flight_needed(ulong land, ulong take, Parameters& parameters) {
        return interval_inside(take, land, parameters.ar_time_min,
                        parameters.ar_time_max) || interval_inside(take, land,
                        parameters.dep_time_min, parameters.dep_time_max)
                        || interval_inside(take, land, parameters.ar_time_max
                                        + parameters.vacation_time_min, parameters.ar_time_max
                                        + parameters.vacation_time_max) || interval_inside(take,
                        land, parameters.dep_time_min - parameters.vacation_time_max,
                        parameters.dep_time_min - parameters.vacation_time_min);
}

void parse_flight(vector<Flight>& flights, cstr line, Parameters &parameters) {
        fill_pos(line);
        if (pos.size() == 7) {
                ulong land_time = convert_string_to_timestamp(get_from_pool(line
                                + pos[4]));
                ulong take_off_time = convert_string_to_timestamp(get_from_pool(line
                                + pos[2]));
                if (!flight_needed(land_time, take_off_time, parameters))
                        return;

                Flight flight;

                flight.from = add_city(line + pos[1]);
                flight.take_off_time = take_off_time;
                flight.to = add_city(line + pos[3]);
                flight.land_time = land_time;
                flight.cost = atof(get_from_pool(line + pos[5]));
                flight.company = add_company(line + pos[6]);

                flight.id = add(get_from_pool(line + pos[0]), id_by_string, id_counter,
                                id_by_index);
                flights.push_back(flight);
        }
}

int add(cstr s, umap &m, int &counter, vector<cstr> &v) {
        umap::iterator i = m.find(s);
        if (i == m.end()) {
                m.insert(make_pair(s, counter));
                v.push_back(s);
                return counter++;
        } else {
                return i->second;
        }
}

void parse_flights(vector<Flight>& flights, File &flights_file,
                Parameters &parameters) {
        flights_file.fopen();
        istream input(flights_file.get_mapped_buf());
        while (!input.eof()) {
                parse_flight(flights, flights_file.read_line(input), parameters);
        }
        flights_file.fclose();
}

void parse_alliance(cstr line) {
        fill_pos(line);
        for (size_t i = 0; i < pos.size(); i++) {
                cstr line_i = get_from_pool(line + pos[i]);
                if (company_by_string.find(line_i) == company_by_string.end()) {
                        continue;
                }
                for (size_t j = 0; j < pos.size(); ++j) {
                        cstr line_j = get_from_pool(line + pos[j]);
                        if (company_by_string.find(line_j) == company_by_string.end()) {
                                continue;
                        }
                        alliances[company_by_string[line_i]][company_by_string[line_j]]
                                        = true;
                }
        }
}

void parse_alliances(File &alliances_file) {
        alliances_file.fopen();
        istream input(alliances_file.get_mapped_buf());
        while (!input.eof()) {
                parse_alliance(alliances_file.read_line(input));
        }
        alliances_file.fclose();
}

void print_alliances(vector<vector<int> > &alliances) {
        for (size_t i = 0; i < alliances.size(); i++) {
                cout << "Alliance " << i << " : ";
                for (size_t j = 0; j < alliances[i].size(); j++) {
                        cout << "**" << alliances[i][j] << "**; ";
                }
                cout << endl;
        }
}

void print_flights(vector<Flight>& flights, ofstream& output) {
        for (size_t i = 0; i < flights.size(); i++)
                print_flight(flights[i], output);
}

void print_travel(Travel& travel, ofstream& output) {
        float cost = 0;
        for (size_t i = 0; i < travel.size(); ++i) {
                if (travel[i].discount > 0.9) {
                        travel[i].discount = 1;
                } else if (travel[i].discount > 0.75) {
                        travel[i].discount = 0.8;
                } else {
                        travel[i].discount = 0.7;
                }
                cost += (travel[i].cost * travel[i].discount);
        }

        output << "Price : " << cost << endl;
        print_flights(travel, output);
        output << endl;
}

void output_play_hard(vector<Travel>& travels, Parameters& parameters) {
        ofstream output;
        output.open(parameters.play_hard_file);
        vector<cstr> &cities = parameters.airports_of_interest;
        for (size_t i = 0; i < travels.size(); i++) {
                output << "“Play Hard” Proposition " << (i + 1) << " : " << cities[i]
                                << endl;
                print_travel(travels[i], output);
                output << endl;
        }
        output.close();
}

void output_work_hard(Travel &travel, Parameters& parameters) {
        ofstream output;
        output.open(parameters.work_hard_file);
        output << "“Work Hard”" << " Proposition :" << endl;
        print_travel(travel, output);
        output.close();
}

void fill_flights_by_cities(vector<Flight*> &flights) {
        flightsByDepartureCities.resize(city_counter);
        flightsByArrivalCities.resize(city_counter);

        for (size_t i = 0; i < flights.size(); ++i) {
                Flight * fl = flights[i];
                flightsByDepartureCities[fl->from].push_back(fl);
                flightsByArrivalCities[fl->to].push_back(fl);
        }

        for (size_t i = 0; i < flightsByDepartureCities.size(); ++i) {
                sort(flightsByDepartureCities[i].begin(),
                                flightsByDepartureCities[i].end(), flightByTakeOffComparator);
                sort(flightsByArrivalCities[i].begin(),
                                flightsByArrivalCities[i].end(), flightByArriveComparator);
        }
}

int main(int argc, char **argv) {
        cstr tz = getenv("TZ");
        setenv("TZ", "", 1);
        tzset();

        Parameters parameters;
        read_parameters(parameters, argc, argv);

        omp_set_num_threads(parameters.nb_threads);

        File flights_file(parameters.flights_file);
        File alliances_file(parameters.alliances_file);

        vector<Flight> flights;
        flights.reserve(1000000);
        parse_flights(flights, flights_file, parameters);

        alliances.resize(company_counter);
        for (int i = 0; i < company_counter; ++i) {
                alliances[i].resize(company_counter);
        }

        parse_alliances(alliances_file);

        vector<Flight*> f(flights.size());
        for (size_t i = 0; i < f.size(); ++i) {
                f[i] = &flights[i];
        }
        fill_flights_by_cities(f);

        create_graphs(f, parameters);
        vector<Travel> travels = solve_task(f, parameters);
        Travel work_hard = travels.back();
        travels.pop_back();
        output_work_hard(work_hard, parameters);
        output_play_hard(travels, parameters);

        if (tz)
                setenv("TZ", tz, 1);
        else
                unsetenv("TZ");
        tzset();

        flights_file.dispose();
        alliances_file.dispose();
}