Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-19

PKU 3804 -- Swimming Jam

| 18:04 | PKU 3804 -- Swimming Jam - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3804 -- Swimming Jam - Wrong Answer -- japlj PKU 3804 -- Swimming Jam - Wrong Answer -- japlj のブックマークコメント

1秒ずつシミュレーションしたらTLEしたので、次に端に到着する人が現れるまでワープさせるようにしたらTLE1秒のところをぴったり1000MSで通った。


#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct swimmer {
  int pos, pace, laps;
  swimmer(int po, int pa, int la)
    : pos(po), pace(pa), laps(la) { }
};
bool operator < (const swimmer& a, const swimmer& b)
{
  return a.pace < b.pace;
}

int main()
{
  int n;
  while(scanf("%d", &n), n) {
    vector<swimmer> a, b;
    for(int i=0; i<n; ++i) {
      int t, c;
      scanf("%d%d", &t, &c);
      a.push_back(swimmer(t, t, c*2));
    }
    sort(a.begin(), a.end());
    int tm;
    for(tm=0; a.size()+b.size()>0; ) {
      int x = a.size()>0 ? a[0].pos : 300;
      int y = b.size()>0 ? b[0].pos : 300;
      if(x > y) x = y;
      for(int i=0; i<(int)a.size(); ++i) a[i].pos-=x;
      for(int i=0; i<(int)b.size(); ++i) b[i].pos-=x;
      tm += x;
      if(a.size()>0 && a[0].pos<=0) {
	int i;
	vector<swimmer> p;
	for(i=0; i<(int)a.size() && a[i].pos<=0; ++i)
	  p.push_back(swimmer(a[i].pace, a[i].pace, a[i].laps-1));
	sort(p.begin(), p.end());
	while(i--) a.erase(a.begin());
	for(i=0; i<(int)p.size(); ++i) b.push_back(p[i]);
      }
      if(b.size()>0 && b[0].pos<=0) {
	int i;
	vector<swimmer> p;
	for(i=0; i<(int)b.size() && b[i].pos<=0; ++i)
	  if(b[i].laps>1)
	    p.push_back(swimmer(b[i].pace, b[i].pace, b[i].laps-1));
	sort(p.begin(), p.end());
	while(i--) b.erase(b.begin());
	for(i=0; i<(int)p.size(); ++i) a.push_back(p[i]);
      }
    }
    printf("%d\n", tm);
  }
  return 0;
}
 |