hashcode-2016/Olivier/main.cpp

#include "instance.h"

using namespace std;

instance ins;

int dist2_wh(const order &a) {
  int r = 1000000000;
  for(int i = 0; i < ins.W; i++) {
    r = min(r, a.p.dist2(ins.wh[i].p));
  }
  return r;
}

bool sort_ord(const order &a, const order &b) {
  if(a.ord.size() == b.ord.size())
    return dist2_wh(a) < dist2_wh(b);
  return a.ord.size() < b.ord.size();
}

int next(instance &ins) {
  int best = -1;
  for(int i = 0; i < ins.orders.size(); i++) {
    if(!ins.orders[i].ord.empty()) {
      best = i;
      break;
    }
  }
  return best;
}

void glouton(instance &ins) {
  sort(ins.orders.begin(), ins.orders.end(), sort_ord);
  cerr << ins.orders[0].ord.size() << endl;
  vector<int> drone_temps(ins.drones);
  vector<pos> drone_pos;
  int score = 0;
  for(int i = 0; i < ins.drones; i++)
    drone_pos.push_back(ins.wh[0].p);
  while(true) {
    int next_i = next(ins);
    if(next_i < 0)
      break;
    int drone = rand()%ins.drones;
    order &ord = ins.orders[next_i];
    assert(!ord.ord.empty());
    pair<const int, int> &type = *ord.ord.begin();
    int quantity = min(type.second, ins.max_load/ins.weights[type.first]);
    int wa = ins.find(drone_pos[drone], type.first, quantity);
    quantity = min(quantity, ins.wh[wa].disp[type.first]);
    ins.wh[wa].disp[type.first] -= quantity;
    // decrease order / stock
    type.second -= quantity;
    if(!type.second)
      ord.ord.erase(type.first);

    // augment drone_temps
    drone_temps[drone] += 1+ceil(sqrt(drone_pos[drone].dist2(ins.wh[wa].p)));
    drone_temps[drone] += 1+ceil(sqrt(ins.wh[wa].p.dist2(ord.p)));
    drone_pos[drone] = ord.p;
    if(drone_temps[drone] > ins.T)
      break;

    // pass order
    cout << drone << " L " << wa << " " << type.first << " " << quantity << endl;
    cout << drone << " D " << ord.id << " " << type.first << " " << quantity << endl;

    // compute score
    score += ceil(10.*(ins.T-drone_temps[drone])/ins.T);
  }
  cerr << "Score : " << score << endl;
}

int main() {
  int seed = time(NULL);
  srand(seed);
  cerr << "seed : " << seed << endl;
  //instance ins;
  glouton(ins);
  return 0;
}