Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*!
- * \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 ¶meters);
- void parse_flights(vector<Flight>& flights, File &flights_file, Parameters ¶meters);
- void parse_alliance(cstr line);
- void parse_alliances(File &alliances_file);
- void print_params(Parameters ¶meters);
- 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 ¶meters) {
- 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 ¶meters) {
- 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 ¶meters) {
- 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();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement