GCJテンプレート

前回日記を書いたときから一回も練習をしていないことに気づいた。
もうすぐそこに迫ってきているというのに。
テキサスに行ったときは
メダルを持ち帰ってきます、などと臆面もなく言っていたが、
今回はとてもじゃないが何も期待できない。
こんなに何もせずに勝てるわけないじゃない。

それはそれとして。
Round2のときにデュアルコアが使えてれば後一問通ったのに、と思って
Round3のときに準備したテンプレートでも公開してみることにする。
Round3が終わったときには、やっぱりプログラムはオーダーだ、
とか思って東京Local大会には持っていかなかったのだが、
計算機の気まぐれで通るという綱渡りになってしまったので、
Finalにはやっぱり持っていこうと思う。
あまり大きなテンプレートはバグが入っていたら怖いから、
できれば避けたかった所なのだが致し方あるまい。

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cctype>

#include <pthread.h>

using namespace std;

//-----

template <class T>
class parallel_scheduler{
public:
  parallel_scheduler(int cpu_num):cpu_num(cpu_num){
    T::init();
    init();
  }

  void go(){
    string line;getline(cin,line);
    int cases=atoi(line.c_str());
    for (int i=1;i<=cases;i++){
      T *t=new T();
      t->read();
      while (running>=cpu_num)
	usleep(10*1000);
      schedule(i,t);
    }
    while(running>0)
      usleep(10*1000);
  }

private:
  void init(){
    running=0;
    next=1;
    pthread_mutex_init(&run_m,NULL);
    pthread_mutex_init(&ans_m,NULL);
  }

  void schedule(int cn,T *t){
    pthread_mutex_lock(&run_m);
    running++;
    pthread_mutex_unlock(&run_m);

    pthread_t tid;
    pair<int,pair<T*,parallel_scheduler*> > *p=
      new pair<int,pair<T*,parallel_scheduler*> >(cn,make_pair(t,this));
    pthread_create(&tid,NULL,start,p);
    pthread_detach(tid);
  }

  static void *start(void *arg){
    pair<int,pair<T*,parallel_scheduler*> > *p=
      (pair<int,pair<T*,parallel_scheduler*> >*)arg;
    int cn=p->first;
    T *t=p->second.first;
    parallel_scheduler *ps=p->second.second;
    delete p;

    ostringstream oss;
    t->solve(oss);
    delete t;

    ps->register_ans(cn,oss.str());
    ps->end();

    return NULL;
  }

  void end(){
    pthread_mutex_lock(&run_m);
    running--;
    pthread_mutex_unlock(&run_m);
  }

  void register_ans(int cn,const string &ans){
    pthread_mutex_lock(&ans_m);
    anss.insert(make_pair(cn,ans));
    while(anss.count(next)!=0){
      cout<<"Case #"<<next<<": "<<anss[next]<<endl;
      anss.erase(next);
      next++;
    }
    pthread_mutex_unlock(&ans_m);
  }

  int cpu_num;
  int running;

  map<int,string> anss;
  int next;

  pthread_mutex_t run_m;
  pthread_mutex_t ans_m;
};

template <class T>
class sequential_scheduler{
public:
  sequential_scheduler(){
    T::init();
  }

  void go(){
    string line;getline(cin,line);
    int cases=atoi(line.c_str());
    for (int i=1;i<=cases;i++){
      T *t=new T();
      t->read();
      ostringstream oss;
      t->solve(oss);
      delete t;
      cout<<"Case #"<<i<<": "<<oss.str()<<endl;
    }
  }
};

//-----

class solver;

#define PARALLEL

int main(int argc,char *argv[])
{
#ifdef PARALLEL
  int cpu_num=2;
  if (argc==2) cpu_num=atoi(argv[1]);
  cerr<<"PAR: "<<cpu_num<<endl;
  parallel_scheduler<solver>(cpu_num).go();
#else
  cerr<<"SEQ:"<<endl;
  sequential_scheduler<solver>().go();
#endif
  return 0;
}

//-----

class solver{
public:
  solver(){
    // テストケースごとの初期化処理
  }
  ~solver(){
    // テストケースごとの終了処理
  }

  static void init(){
    // 全体の初期化処理
  }

  void read(){
    // テストケースをcinから読み込む
  }

  void solve(ostream &cout){
    // 解く。出力は引数のcoutに。
  }
};

スレッド数の指定と、万一の時のための自明なコードによる逐次版を用意。
テストケースを読み込みながら、CPUが埋まっていなければそのテストケースをスケジュールする。
埋まってたらどれかが空くまで待機。
出力はバッファして、先頭から順に確定し次第出力。
例外のこととか何も考えられていないな。だがそれがいい。
さて、ライブラリを作る作業をせねば…。