Market_Simulation

#include <cstdint>
#include <random>
#include <vector>
#include <queue>
#include <cassert>
#include <algorithm>
#include <utility>
#include <tuple>
#include <iostream>

using namespace std;

// Please disable before submitting.
constexpr bool kDebug = false;

using Side = bool;
constexpr bool BUY = true;
constexpr bool SELL = false;

struct order {
  uint64_t order_token;
  uint64_t shares;
  double price;
  Side side; // false = sell, true = buy
  uint64_t created_at;
  uint64_t cancelled_or_executed_at;
  void Print() const {
    auto& o = *this;
    std::cerr << "O," << o.order_token << ", price = " << o.price << ", shares = " << o.shares
              << ", " << (o.side ? "BUY" : "SELL") << ", time = " << o.created_at << ", timeout = "
              << o.cancelled_or_executed_at << "\n";

  }
};

using QueueItem = order;

struct query {
  uint64_t query_time;
};

enum Type {CANCEL = 0, BUY_SELL = 1, GET_INFO = 2};

struct OverAllQuery {
  Type type;
  uint64_t timestamp;
  int index;
  void Print() const {
    std::cout << "Query{type = " << int(type) << ", timestamp = " << timestamp
              << ", index = " << index << "}" << std::endl;
  }

};


struct BuyerCmp {
  bool operator()(const QueueItem& a, const QueueItem& b) {
    return std::make_pair(a.price, -a.created_at) < std::make_pair(b.price, -b.created_at);
  }
};

struct SellerCmp {
  bool operator()(const QueueItem& a, const QueueItem& b) {
    return std::make_pair(-a.price, -a.created_at) < std::make_pair(-b.price, -b.created_at);
  }
};

// highest prince on top.
using BuyerQueue = std::priority_queue<QueueItem, std::vector<QueueItem>, BuyerCmp>;

// lowest price on top.
using SellerQueue = std::priority_queue<QueueItem, std::vector<QueueItem>, SellerCmp>;

struct PerShare {
    template<typename MyQueue, typename OppositeQueue>
    void MatchOrder(order oinfo, MyQueue& my_queue, OppositeQueue& queue) {
        while(oinfo.shares > 0 && queue.size() > 0) {
            if (oinfo.side == BUY) {
                if (queue.top().price > oinfo.price) break;
            } else  {
                if (queue.top().price < oinfo.price) break;
            }
            auto top = queue.top();
            queue.pop();
            if (top.cancelled_or_executed_at <= oinfo.created_at) continue;
            int matched_size = std::min(top.shares, oinfo.shares);
            // std::cout << "Matched " << matched_size << " shares, with order_token = " << top.order_token << std::endl;
            oinfo.shares -= matched_size;
            top.shares -= matched_size;
            num_outstanding_shares -= matched_size;
            outstanding_shares_of_order[top.order_token] -= matched_size;
            if (top.shares > 0) {
                queue.push(top);
            }
        }
        if (oinfo.shares > 0) {
            my_queue.push(oinfo);
            num_outstanding_shares += oinfo.shares;
            outstanding_shares_of_order[oinfo.order_token] = oinfo.shares;
            // std::cout << "Put in queue = " << oinfo.shares << " shares." << std::endl;
        }
    }

    void MakeOrder(order oinfo) {
        if (oinfo.side == BUY) {
            MatchOrder(oinfo, buyer_queue, seller_queue);
        } else if (oinfo.side == SELL) {
            MatchOrder(oinfo, seller_queue, buyer_queue);
        } else {
            assert(false);
        }
    }

    void MakeOverallQuery(const OverAllQuery& q) {
      // std::cout << "\n\nts = " << q.timestamp << std::endl;
      if (q.type == CANCEL) {
        num_outstanding_shares -= outstanding_shares_of_order[q.index];
        // std::cout << "CANCEL: ";
        // orders[q.index].Print();
      } else if (q.type == GET_INFO) {
        output_info[q.index] = num_outstanding_shares;
        // std::cout << "GET_INFO = " << output_info[q.index] << std::endl;
      } else if (q.type == BUY_SELL) {
        // std::cout << "MakeOrder: ";
        // orders[q.index].Print();
        MakeOrder(orders[q.index]);
      } else {
        assert(false);
      }
      // std::cout << "num_outstanding_shares = " << num_outstanding_shares << std::endl;
    }

    PerShare(const vector<order> &orders, vector<uint64_t>& output_info)
      : orders(orders), output_info(output_info), outstanding_shares_of_order(orders.size(), 0) { }
    const vector<order> &orders;
    vector<uint64_t>& output_info;
    std::vector<uint64_t> outstanding_shares_of_order;
    BuyerQueue buyer_queue;
    SellerQueue seller_queue;
    uint64_t num_outstanding_shares = 0;
};


std::vector<uint64_t> your_solution(const vector<order> &orders,
                                    const vector<query> &queries) {
  std::vector<OverAllQuery> overall_queries;
  for (int i = 0; i < int(orders.size()); i++) {
    auto& o = orders[i];
    if (o.cancelled_or_executed_at <= o.created_at) continue;
    overall_queries.push_back(OverAllQuery{BUY_SELL, o.created_at, i});
    overall_queries.push_back(OverAllQuery{CANCEL, o.cancelled_or_executed_at, i});
  }
  for (int i = 0; i < int(queries.size()); i++) {
    auto& q = queries[i];
    overall_queries.push_back(OverAllQuery{GET_INFO, q.query_time, i});
  }
  std::sort(overall_queries.begin(), overall_queries.end(),
    [](const OverAllQuery& a, const OverAllQuery& b){
    return std::make_pair(a.timestamp, a.type)
               < std::make_pair(b.timestamp, b.type);
  });
  vector<uint64_t> output_info(queries.size());
  PerShare per_share(orders, output_info);
  for (auto& x : overall_queries) {
    per_share.MakeOverallQuery(x);
  }
  return output_info;
}

///////////////////////////////////////////////////////////////////////////////
// Please do not change any code below.                                      //
///////////////////////////////////////////////////////////////////////////////

std::pair<vector<order>, vector<query>> gen_input(int seed) {
  mt19937 gen(seed);

  const uint64_t order_len = 1 << (gen() % 20);
  const uint64_t time_len = 1 << (gen() % 20);

  vector<order> orders;
  for (uint64_t i = 0; i < order_len; ++i) {
    const double duration = std::max(1.0, time_len / std::log2(time_len));
    const uint64_t start = gen() % time_len;
    const uint64_t end = std::min<int>(start + duration, time_len);
    order o{
        .order_token = i,
        .shares = static_cast<uint64_t>(gen() % 10000),
        .price = static_cast<double>(gen() % 1000) / 10,
        .side = gen() % 2 ? false : true,
        .created_at = start,
        .cancelled_or_executed_at = end,
    };
    orders.emplace_back(o);
  }

  vector<query> queries;
  for (uint64_t i = 0; i < order_len; ++i) {
    query q{
        .query_time = static_cast<uint64_t>(gen() % time_len),
    };
    queries.emplace_back(q);
  }

  return {std::move(orders), std::move(queries)};
}

int hash_result(const std::vector<uint64_t> &answers) {
  std::hash<uint64_t> hasher;
  uint64_t result = 0;
  for (auto &a : answers) {
    result = hasher(a) ^ (result << 1);
  }
  return result;
}

// This test harness generates an input to and hashes the output from your
// solution. Please do not change any code below this line.
int solution(int seed) {
  auto input = gen_input(seed);
  bool debug = kDebug && input.first.size() < 100 && input.second.size() < 100;
  if (debug) {
    for (auto &o : input.first) {
      std::cerr << "O," << o.order_token << "," << o.price << "," << o.shares
                << "," << (o.side ? 'B' : 'S') << "," << o.created_at << ","
                << o.cancelled_or_executed_at << "\n";
    }
    for (auto &q : input.second) {
      std::cerr << 'Q' << "," << q.query_time << "\n";
    }
  }

  const auto answers = your_solution(input.first, input.second);

  if (debug) {
    for (auto &a : answers) {
      std::cerr << "R," << a << "\n";
    }
  }

  return hash_result(answers);
}