hashcode-2016/Olivier/main.cpp

#include "instance.h"

using namespace std;

instance ins;

pos drone_pos;

int order_d(const order &o) {
  int d = -1;
  int poids = 0;
  int best_wh = -1;
  if(o.ord.empty())
    return 2000000000; // INF
  for(auto item : o.ord) {
    poids += item.second*ins.weights[item.first];
  }
  for(int i = 0; i < ins.W; i++) {
    bool ok = false;
    for(pair<int, int> item : o.ord) {
      if(ins.wh[i].disp[item.first] > 0) {
        ok = true;
        break;
      }
    }
    if(ok) {
      int d2 = drone_pos.dist2(ins.wh[i].p) + ins.wh[i].p.dist2(o.p);
      if(d < 0 || d2 < d) {
        d = d2;
        best_wh = i;
      }
    }
  }

  if(d < 0) {
    cerr << "! d < 0" << endl;
    return 2000000000; // INF
  }
  if(poids > ins.max_load)
    d += ins.col*ins.col + ins.row*ins.row;

  ins.orders[o.id].best_wh = best_wh; // (o is const)
  return d;
}

bool cmp_ord(const order &a, const order &b) {
  return order_d(a) < order_d(b);
}

class drone {
  public:
    drone(int id, pos p) : id(id), temps(0), p(p) {}
    int id;
    int temps;
    pos p;
    bool operator<(const drone &b) const {
      return temps > b.temps;
    }
};

void glouton(instance &ins) {
  int score = 0;
  priority_queue<drone> Q;

  for(int i = 0; i < ins.drones; i++)
    Q.push(drone(i, ins.wh[0].p));

  while(!Q.empty()) {
    drone dr = Q.top();
    Q.pop();

    drone_pos = dr.p;
    order &ord = *min_element(ins.orders.begin(), ins.orders.end(), cmp_ord);

    if(ord.ord.empty())
      break;

    assert(ord.best_wh >= 0);
    int wa = ord.best_wh;

    // augment dr.temps
    dr.temps += 1+ceil(sqrt(dr.p.dist2(ins.wh[wa].p)));
    dr.temps += 1+ceil(sqrt(ins.wh[wa].p.dist2(ord.p)));
    dr.p = ord.p;
    if(dr.temps > ins.T) {
      continue;
    }

    // planifie l'ordre
    int load = 0;
    vector<pair<int, int>> aprendre;
    for(pair<int, int> item : ord.ord) {
      assert(load <= ins.max_load);
      if(load == ins.max_load)
        break;
      int q = min(item.second, ins.wh[wa].disp[item.first]);
      q = min(q, (ins.max_load-load)/ins.weights[item.first]);
      if(q > 0) {
        aprendre.push_back(make_pair(item.first, q));
        load += ceil(q*ins.weights[item.first]);
      }
    }

    if(aprendre.empty())
      cerr << "! aprendre is empty" << endl;

    // pass order
    for(pair<int, int> item : aprendre) {
      // decrease order / stock
      ins.wh[wa].disp[item.first] -= item.second;
      ord.ord[item.first] -= item.second;
      if(!ord.ord[item.first])
        ord.ord.erase(item.first);

      cout << dr.id << " L " << wa << " " << item.first << " " << item.second << endl;
    }
    for(pair<int, int> item : aprendre) {
      cout << dr.id << " D " << ord.id << " " << item.first << " " << item.second << endl;
    }

    // push again drone
    Q.push(dr);

    // compute score
    if(ord.ord.empty())
      score += ceil(100.*(ins.T-dr.temps)/(double)ins.T);
  }



  cerr << "Score : " << score << endl;
}

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