// Copyright 2003 Jared Showalter <jareds@mit.edu>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<fstream>
#include<iostream>

using namespace std;

double normal_rand() {
  static bool avail = false;
  static double next;
  if (avail) {
    avail = false;
    return next;
  } else {
    double a, b, c;
    do {
      a = 2 * drand48() - 1;
      b = 2 * drand48() - 1;
      c = a * a + b * b;
    } while (c >= 1 || c == 0);
    double m = sqrt(-2 * log(c) / c);
    next = m * a;
    avail = true;
    return m * b;
  }
}

const int numRounds = 6;
const int roundSizes[numRounds] = {500, 200, 100, 50, 16, 4};
const int roomCounts[numRounds - 1] = {50, 20, 10, 5, 4};
const int numStats = numRounds + roundSizes[numRounds - 1];

class coder {
public:
  const int cid;
  const int rating;
  const int vol;
  const int seed;
  vector<int> stats;
  double perf;
  coder(int c, int r, int v, int s) :
    cid(c), rating(r), vol(v), seed(s),
    stats(vector<int>(numStats, 0)) { }
  inline void setPerformance() {
    perf = rating + vol * normal_rand();
  }
};
typedef coder* coderptr;

double part_perf = 0;
class perf_pred {
public:
  inline bool operator()(coderptr c) {
    return c->perf > part_perf;
  }
} perf_pred;

class SeedCompare {
public:
  inline bool operator()(coderptr a, coderptr b) {
    return a->seed < b->seed;
  }
} seedCompare;

class PerfCompare {
public:
  inline bool operator()(coderptr a, coderptr b) {
    return a->perf > b->perf;
  }
} perfCompare;

class TCSimulation {
public:
  typedef vector<coderptr>  vc;
  typedef vc::iterator vci;
  vector<vc> rounds;
  vc coders;
  int startRound;

  int doneTrials;
  char * checkpoint;
  static const int cpMask = 0xffff;

  void loadCheckpoint() {
    ifstream in(checkpoint);
    int cid, rating, vol, seed = 0;
    if (!in.is_open()) return;
    in >> doneTrials;
    in >> cid >> rating >> vol;
    while (!in.eof()) {
      coderptr c = new coder(cid, rating, vol, ++seed);
      for (int j = 0; j < numStats; j++)
        in >> c->stats[j];
      coders.push_back(c);
      in >> cid >> rating >> vol;
    }
    in.close();
  }

  void saveCheckpoint() {
    cout << "Saving checkpoint at " << doneTrials << "\n";
    ofstream o(checkpoint);
    o << doneTrials << "\n";
    for (uint i = 0; i < coders.size(); i++) {
      coderptr c = coders[i];
      o << c->cid << " " << c->rating << " " << c->vol;
      for (int j = 0; j < numStats; j++)
        o << " " << c->stats[j];
      o << "\n";
    }
    o.close();
  }

  TCSimulation(char * chkpt) {
    checkpoint = chkpt;
    loadCheckpoint();
    int sr = -1;
    for (int i = 0; i < numRounds; i++)
      if (roundSizes[i] == (int) coders.size()) sr = i;
    if (sr < 0) throw "Wrong numbers of coders";
    startRound = sr;
    for (int i = 0; i < numRounds; i++)
      rounds.push_back(vc(roundSizes[i]));
  }

  static void partitionByIndex(vci lo, vci hi, vci goal) {
    vci p;
    do {
      part_perf = (*(lo + rand() % (hi - lo)))->perf;
      p = partition(lo, hi, perf_pred);
      if (p < goal) lo = p; else hi = p;
    } while (p != goal);
  }

  void doNormalRound(vc &src, vc &dst, int round) {
    int n = src.size();
    int m = dst.size();
    int rooms = roomCounts[round];
    int r2 = rooms * 2;
    for (int i = 0; i < n; i++)
      src[i]->setPerformance();
    for (int i = 0; i < rooms; i++) {
      double max = src[i]->perf;
      int best = i;
      int k = r2 - 1 - i;
      for (int j = 0; j < n; j += r2) {
        if (i + j < n && src[i + j]->perf > max) {
          max = src[i + j]->perf;
          best = i + j;
        }
        if (k + j < n && src[k + j]->perf > max) {
          max = src[k + j]->perf;
          best = k + j;
        }
      }
      if (best != i) swap(src[i], src[best]);
    }
    if (round == numRounds - 1) {
      copy(src.begin(), src.begin() + m, dst.begin());
    } else {
      partitionByIndex(src.begin() + rooms, src.begin() + n, src.begin() + m);
      copy(src.begin(), src.begin() + m, dst.begin());
      sort(dst.begin(), dst.end(), seedCompare);
    }
    if (round == startRound) return;
    for (int i = m; i < n; i++)
      src[i]->stats[round]++;
  }

  void doFinalRound(vc &round) {
    for (uint i = 0; i < round.size(); i++)
      round[i]->setPerformance();
    sort(round.begin(), round.end(), perfCompare);
    int j = numStats;
    for (uint i = 0; i < round.size(); i++) {
      round[i]->stats[--j]++;
    }
  }

  void doTournament(int trials) {
    int dt = doneTrials;
    for (int i = 0; i < trials; i++) {
      if ((i & cpMask) == 0) {
        doneTrials = dt + i;
        if (checkpoint != "") {
          saveCheckpoint();
        }
      }
      copy(coders.begin(), coders.end(), rounds[startRound].begin());
      for (int j = startRound; j < numRounds - 1; j++)
        doNormalRound(rounds[j], rounds[j + 1], j);
      doFinalRound(rounds[numRounds - 1]);
    }
    doneTrials = dt + trials;
    saveCheckpoint();
  }

};

void init_rand() {
  unsigned short seed[3];
  unsigned int seed2;
  ifstream rnd("/dev/random");
  if (rnd.rdbuf()->sgetn((char *) seed, sizeof(seed)) != sizeof(seed))
    throw "Reading random a";
  seed48(seed);
  if (rnd.rdbuf()->sgetn((char *) &seed2, sizeof(seed2)) != sizeof(seed2))
    throw "Reading random b";
  srand(seed2);
}

int main(int argc, char ** argv) {
  if (argc < 3) {
    cout << "Usage: tc-simulation <checkpoint> <trials>\n";
    return 0;
  }
  int trials = atoi(argv[2]);
  TCSimulation * s;
  try {
    s = new TCSimulation(argv[1]);
    if (s->doneTrials >= trials) return 0;
    init_rand();
  } catch (const char * str) {
    cerr << str << "\n";
    return 1;
  }

  trials -= s->doneTrials;
  s->doTournament(trials);
  return 0;
}