RCO presents 日本橋ハーフマラソン 本戦 (オープン)

Submission #1177600

Source codeソースコード

#include <iostream>
#include <cstdlib>

#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <iostream>
#include <fstream>
#include <unistd.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include "sys/time.h"
using namespace std;
#define ITER(l,i) for(decltype(l.begin()) i=l.begin();i!=l.end();i++)
#define HERE (cerr << "LINE: " << __LINE__ << endl)

typedef long long ll_t;
typedef unsigned long long ull_t;

#ifdef LOCAL
#define msg(x) (x)
#else
#define msg(x)
#endif

#define DBG(x) cerr << #x << ": " << x << endl

struct timeval timer_begin, timer_end;
int timer_called;
inline void timer_start() 
{
  timer_called++;
  gettimeofday(&timer_begin, NULL);    
}     
inline double timer_now() 
{         
  timer_called++;
  gettimeofday(&timer_end, NULL);         
  return timer_end.tv_sec - timer_begin.tv_sec +
    (timer_end.tv_usec - timer_begin.tv_usec)/1000000.0;     
}

template<class T>
const T& clamp(const T& v,const T& lo,const T& hi) {
  return (v < lo) ? lo : (v > hi) ? hi : v;
}
unsigned int hash_function(unsigned long p) {
  // xor32()
  p ^= p<<7;
  p ^= p>>1;
  p ^= p<<25;
  unsigned int c = __builtin_popcount(p);
  return p<<c | p>>(32-c);
}
unsigned long long hash_function64(unsigned long long p) {
  // xor64()
  p ^= p<<16;
  p ^= p>>7;
  p ^= p<<39;
  unsigned long long c = __builtin_popcount(p);
  return p<<c | p>>(64-c);
}  

struct xor128_t {
  unsigned long long x, y, z, w;

  xor128_t(int seed=0) : x(123456789^seed) , y(362436069), z(521288629), w(88675123) {
    for (int i=0; i<48; i++)
      get();
  }

  void init(int seed) {
    x = 123456789^seed;
    y = 362436069;
    z = 521288629;
    w = 88675123;

    for (int i=0; i<48; i++)
      get();
  }

  inline unsigned long long get() {
    unsigned long long t=(x^(x<<11)); x=y; y=z; z=w;
    return (w=(w^(w>>19))^(t^(t>>8)));
  }

  inline unsigned long long get(unsigned int sz) {
    if (sz <= 1)
      return 0;

    unsigned long long x;
    const unsigned long long mask = (1<<(ilogb(sz-1)+1)) - 1;
    //cout << sz << " " << mask << endl;
    assert(mask >= (sz-1) && mask < 2*sz-1);
    do {
      x = get() & mask;
    } while (x >= sz);

    return x;
  }

  inline unsigned long long get(int beg,int end) {
    return get(end-beg) + beg;
  }

  double get_double() {
    static const double double_factor = 1.0 / (1.0 + 0xffffffffffffffffuLL);
    return get() * double_factor;
  }

  template<typename T> void shuffle(vector<T>& v,int partial=-1) {
    int sz = v.size();
    if (partial < 0 || partial > sz)
      partial = sz;

    for (int i=0; i<partial; i++) {
      swap(v[i], v[i + get(sz-i)]);
    }

  }
};

struct uf_t {
  vector <int16_t> parent;

  void clear() {
    parent.clear();
  }

  void add(int elm) {
    if (elm >= parent.size()) 
      parent.resize(elm+1, -1);
  }

  void merge(int a,int b) {
    add(a);
    add(b);

    int ia = a;
    int ib = b;

    if ((ia^ib)&1) swap(ia, ib);  // ok?
      
    int ra = root(ia);
    int rb = root(ib);

    if (ra != rb) {
      parent[ra] += parent[rb];
      parent[rb] = ra;
    }
  }

  int size(int elm) {
    return -parent[root(elm)];
  }

  int id(int elm) {
    return root(elm);
  }

  int root(int ia) {
    add(ia);
    return (parent[ia] < 0) ? ia : (parent[ia] = root(parent[ia]));
  }
};

template <typename Score_t,typename Item_t,typename HashFunc_t>
struct best_k_t {
  vector<pair<Score_t,int>> v;
  vector<Item_t> items;
  HashFunc_t hashfunc;
  set<uint32_t> used;
  bool never_push;

  best_k_t() : never_push(false) {}

  void push_force(const Score_t sc,const Item_t& e) {
    int id = items.size();
    items.push_back(e);

    int n = v.size();
    v.push_back(pair<Score_t,int>(sc,id));

    int m = (n+1)/2 - 1;
    while (n > 0 && v[n] < v[m]) {
      swap(v[n], v[m]);
      n = m;
      m = (n+1)/2 - 1;
    }
  }

  bool push(const Score_t sc,const Item_t& e,int w) {
    assert(!never_push);
    if (v.size() < w) {
      auto h = hashfunc(e);
      if (!used.count(h)) {
	used.insert(h);
	push_force(sc, e);
	return true;
      } else {
	return false;
      }
    } else if (sc > v[0].first) {
      auto h = hashfunc(e);
      if (!used.count(h)) {
	int id = v[0].second;
	v[0].first = sc;
	items[id] = e;
	used.insert(h);
	rebuild();
	return true;
      } else {
	return false;
      }
    }
    return false;
  }

  bool match(const Score_t sc,int w) {
    return (v.size() < w || sc > v[0].first);
  }

  void rebuild() {
    int n = 0;
    while (true) {
      int L = (n+1)*2 - 1;
      int R = L+1;

      if (L >= v.size()) 
	break;

      int m = (R >= v.size() || v[L] < v[R]) ? L : R;

      if (v[m] < v[n]) {
	swap(v[m], v[n]);
	n = m;
      } else {
	break;
      }
    }
  }

  Item_t pop() {
    // fix me
    never_push = true;
    
    int id = v[0].second;
    Item_t ret = items[id];

    v[0] = v.back();
    v.pop_back();

    rebuild();

    return ret;
  }
  Item_t top() { return v[0].second; }

  Item_t best() const {
    int best_i = 0;
    for (int i=0; i<v.size(); i++) {
      if (v[i] < v[best_i])
	best_i = i;
    }
    return items[v[best_i].second];
  }

  void clear() { v.clear(); }
  bool empty() const { return v.empty(); }
  int size() const { return v.size(); }
};

template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[ ";
  for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " ]"; 
  return os; 
}
template<typename T> ostream& operator<<(ostream& os, const set<T>& v) {
  os << "{ ";
  for(typename set<T>::const_iterator it=v.begin(); it!=v.end(); ++it) {
    if (it != v.begin())
      os << ", ";
    os << *it; 
  }
  os << " }"; 
  return os; 
}
template<typename T1,typename T2> ostream& operator<<(ostream& os, const pair<T1,T2>& v) {
  os << "[ " << v.first << ", " << v.second << "]";
  return os; 
}

#ifdef LOCAL
double TIME_LIMIT_FACTOR = 0.55;
#else
double TIME_LIMIT_FACTOR = 1.0;
#endif
double TIME_LIMIT = TIME_LIMIT_FACTOR * 4.0;

/* insert here */
struct car_t {
  int id;
  int ix, iy, tx, ty;
  int x, y;
  car_t() {}
  car_t(int id,int a, int b,int c,int d) : id(id) {
    ix = b-1;
    iy = a-1;
    tx = d-1;
    ty = c-1;

    x = ix;
    y = iy;
  }
  bool finished() const {
    return x == tx && y == ty;
  }
  
  static bool less_tyx(const car_t& a,const car_t& b) {
    return (a.ty != b.ty) ? (a.ty < b.ty) : (a.tx < b.tx);
  }

  static bool less_txy(const car_t& a,const car_t& b) {
    return (a.tx != b.tx) ? (a.tx < b.tx) : (a.ty < b.ty);
  }

  int cost() const {
    return abs(tx - x) + abs(ty - y);
  }
};
ostream& operator<<(ostream& os,const car_t& car) {
  os << "#" << car.id
     << "(" << car.x << " " << car.y << ")"
     << "->(" << car.tx << " " << car.ty << ")";
  return os;
}

struct point_t {
  int x, y;
  point_t() {}
  point_t(int x,int y) : x(x), y(y) {}
  int manhattan(const point_t& o) const { return abs(x-o.x)+abs(y-o.y); }
};

int H, W, K, T;
int cp(int x,int y) { return y*W+x; }

double score_function(int t,const vector<car_t>& cars) {
  double pd = 20;
  for (const auto& car : cars) {
    pd += abs(car.tx - car.x) + abs(car.ty - car.y);
  }
  double pt = 10 + t * 0.01;

  return 10000000 / (pd * pt);
}

bool move_or_stay(int id,char dir,
		  vector<car_t>& cars,
		  vector<vector<int>>& cur,
		  vector<vector<int>>& nxt,
		  string& moves) {
  if (id < 0 || id >= K || moves[id] != '*')
    return false;
  
  assert(dir == 'R' || dir == 'L' || dir == 'D' || dir == 'U' || dir == '-');
  auto& car(cars[id]);
  int dx = (dir == 'R') ? 1 : (dir == 'L') ? -1 : 0;
  int dy = (dir == 'D') ? 1 : (dir == 'U') ? -1 : 0;
  int nx = car.x + dx;
  int ny = car.y + dy;
  if (nx < 0 || nx >= W || ny < 0 || ny >= H ||
      cur[ny][nx] >= 0 || nxt[ny][nx] >= 0) {
    moves[id] = '-';
    nxt[car.y][car.x] = id;
    return false;
  }
  assert(dir != '-');

  car.x = nx;
  car.y = ny;
  nxt[ny][nx] = id;
  moves[id] = dir;

  return true;
}

bool move_if_possible(int id,char dir,
		  vector<car_t>& cars,
		  vector<vector<int>>& cur,
		  vector<vector<int>>& nxt,
		  string& moves) {
  if (id < 0 || id >= K || moves[id] != '*')
    return false;
  
  assert(dir == 'R' || dir == 'L' || dir == 'D' || dir == 'U' || dir == '-');
  auto& car(cars[id]);
  int dx = (dir == 'R') ? 1 : (dir == 'L') ? -1 : 0;
  int dy = (dir == 'D') ? 1 : (dir == 'U') ? -1 : 0;
  int nx = car.x + dx;
  int ny = car.y + dy;
  if (nx < 0 || nx >= W || ny < 0 || ny >= H ||
      cur[ny][nx] >= 0 || nxt[ny][nx] >= 0) {
    return false;
  }
  assert(dir != '-');

  car.x = nx;
  car.y = ny;
  nxt[ny][nx] = id;
  moves[id] = dir;

  return true;
}

void rotate(int left,int top,int right,int bottom,
	    vector<car_t>& cars,
	    vector<vector<int>>& cur,
	    vector<vector<int>>& nxt,
	    string& moves,
	    const set<int> ignores = set<int>()) {

  for (int x=left; x<right; x++) {
    int id = cur[top][x];
    if (id >= 0 && !ignores.count(id))
      move_if_possible(id, 'R', cars, cur, nxt, moves);
  }

  for (int y=top; y<bottom; y++) {
    int id = cur[y][right];
    if (id >= 0 && !ignores.count(id))
      move_if_possible(id, 'D', cars, cur, nxt, moves);
  }

  for (int x=right; x>left; x--) {
    int id = cur[bottom][x];
    if (id >= 0 && !ignores.count(id))
      move_if_possible(id, 'L', cars, cur, nxt, moves);
  }

  for (int y=bottom; y>top; y--) {
    int id = cur[y][left];
    if (id >= 0 && !ignores.count(id))
      move_if_possible(id, 'U', cars, cur, nxt, moves);
  }

}

vector<point_t> assign(const vector<point_t>& from,vector<point_t> to) {
  assert(from.size() == to.size());
  int n = from.size();
  while (true) {
    int g = 0;
    for (int i=0; i<n; i++)
      for (int j=0; j<n; j++) {
	int cost_ii = from[i].manhattan(to[i]);
	int cost_jj = from[j].manhattan(to[j]);
	int cost_old = cost_ii + cost_jj;
	int cost_ij = from[i].manhattan(to[j]);
	int cost_ji = from[j].manhattan(to[i]);
	int cost_new = cost_ij + cost_ji;
	if (cost_new < cost_old ||
	    cost_new == cost_old && min(cost_ij, cost_ji)>min(cost_ii, cost_jj)) {
	  g += cost_old - cost_new;
	  swap(to[i], to[j]);
	}
      }
    if (g == 0)
      break;
  }

  return to;
}
vector<point_t> assign(const vector<car_t>& cars,const vector<point_t>& ps) {
  vector<point_t> from(cars.size());
  for (int i=0; i<cars.size(); i++)
    from[i] = point_t(cars[i].x, cars[i].y);
  
  return assign(from, ps);
}

vector<string> solve_greedy(vector<car_t> cars) {
  vector<vector<int>> cur(H, vector<int>(W, -1));
  vector<vector<int>> nxt(H, vector<int>(W, -1));
  vector<vector<int>> goal(H, vector<int>(W, -1));
  for (const auto car: cars) {
    cur[car.y][car.x] = car.id;
    goal[car.ty][car.tx] = car.id;
  }
  auto mid(goal);
  {
    int sz = 0;
    for (int x=0; x<W; x++) {
      int c = 0;
      for (int y=0; y<H; y++)
	c += (cur[y][x] >= 0);
      sz = max(sz, c);
    }
      
    for (int x=0; x<W; x++) 
      for (int y=H-1, c=0; c<H-1; c++) {
	if (mid[y][x] < 0) {
	  for (int k=y; k>0; k--) 
	    swap(mid[k][x], mid[k-1][x]);
	} else {
	  y--;
	}
      }

#if 0    
    for (int x=0; x<W; x++) 
      while (mid[H-sz][x] < 0) {
	for (int k=H-sz; k<H-1; k++) 
	  swap(mid[k][x], mid[k+1][x]);
      }
#endif
  }

  vector<int> mx(K), my(K);
  for (int y=0; y<H; y++)
    for (int x=0; x<W; x++) {
      int id = mid[y][x];
      if (id >= 0) {
	mx[id] = x;
	my[id] = y;
      }
    }

  vector<int> rx(K);
  vector<int> sx(K);
  {
    for (int y=0; y+3<H; y+=4) {
      vector<car_t> ord;
      for (int dy=0; dy<4; dy++)
	for (int x=0; x<W; x++) {
	  if (cur[y+dy][x] >= 0)
	    ord.push_back(cars[cur[y+dy][x]]);
	}
      sort(ord.begin(), ord.end(), car_t::less_txy);
      cerr << ord.size()/2+1 << endl;
      for (int i=0; i<ord.size(); i++) {
	rx[ord[i].id] = 1 + i*(W-2)/ord.size();
      }
    }
  }


  vector<string> sol;
  xor128_t rng;
  int best_t = -1;
  double best_score = 0;

  int target_y = H-1;
  enum phase_t {
    PHASE_SORT_SETUP,
    PHASE_SORT,
    PHASE_UP,
    PHASE_MID,
    PHASE_FINISH,
    PHASE_DONE,
  };
  phase_t phase = PHASE_SORT_SETUP;
  vector<point_t> v;
  for (int y=1; y<H; y+=2)
    for (int x=0; x<W; x++)
      v.emplace_back(x, y);
  auto as = assign(cars, v);
  {
    ofstream ofs("as.txt");
    ofs << "30 30 450 10000" << endl;
    for (int i=0; i<K; i++)
      ofs << cars[i].y+1 << " " << cars[i].x+1 << " " << as[i].y+1 << " " << as[i].x+1 << endl;
  }

  for (int t=0; t<T; t++) {
    {
      bool error_found = false;
      for (const auto& car : cars) {
	if (cur[car.y][car.x] != car.id) {
	  error_found = true;
	  cerr << "t: " << t << " " << car << " " << cur[car.y][car.x] << endl;
	}
      }
      if (error_found)
	break;
      for (const auto& car : cars) {
	assert(cur[car.y][car.x] == car.id);
      }
    }
    string moves(K, '*');

    int sort_y = 1;
    if (false && phase == PHASE_SORT_SETUP) {
      int c = 0;
      for (int id=0; id<K; id++) {
	if (cars[id].y != 1 || cars[id].y == 1 && cur[0][cars[id].x] >= 0)
	  move_or_stay(id, 'D', cars, cur, nxt, moves);
	else
	  move_or_stay(id, '-', cars, cur, nxt, moves);	  
	c += (cars[id].y == 0 || cars[id].y == 2);
      }
      if (c == 0) {
	phase = PHASE_SORT;
      }
    } else if (phase == PHASE_SORT_SETUP) {
      int c = 0;
      for (int id=0; id<K; id++) {
	const auto& car(cars[id]);
	if (car.x == as[id].x && car.y == as[id].y) {
	  move_or_stay(id, '-', cars, cur, nxt, moves);
	} else {
	  c++;
	  if (car.x != as[id].x) 
	    move_if_possible(id, "LR"[car.x < as[id].x], cars, cur, nxt, moves);
	  if (car.y != as[id].y)
	    move_if_possible(id, "UD"[car.y < as[id].y], cars, cur, nxt, moves);
	  if (t>0 && moves[id] == '*') {
	    if (car.y < as[id].y && cur[car.y+1][car.x] == nxt[car.y+1][car.x]) {
	      cerr << t << " " << id << " " << cur[car.y+1][car.x] << endl;
	      swap(as[id], as[cur[car.y+1][car.x]]);
	    } else if (car.y > as[id].y && cur[car.y-1][car.x] == nxt[car.y-1][car.x]) {
	      cerr << t << " " << id << " " << cur[car.y-1][car.x] << endl;
	      swap(as[id], as[cur[car.y-1][car.x]]);
	    } else if (car.x < as[id].x && cur[car.y][car.x+1] == nxt[car.y][car.x+1]) {
	      cerr << t << " " << id << " " << cur[car.y][car.x+1] << endl;
	      swap(as[id], as[cur[car.y][car.x+1]]);
	    } else if (car.x > as[id].x && cur[car.y][car.x-1] == nxt[car.y][car.x-1]) {
	      cerr << t << " " << id << " " << cur[car.y][car.x-1] << endl;
	      swap(as[id], as[cur[car.y][car.x-1]]);
	    }
	  }
	  move_or_stay(id, '-', cars, cur, nxt, moves);
	}
      }
      if (c == 0 || t > 10) {
	phase = PHASE_SORT;
	for (int y=0; y+1<H; y++) {
	  vector<car_t> ord;
	  for (int x=0; x<W; x++) {
	    if (nxt[y][x] >= 0)
	      ord.push_back(cars[nxt[y][x]]);
	    if (nxt[y+1][x] >= 0)
	      ord.push_back(cars[nxt[y+1][x]]);
	  }
	  sort(ord.begin(), ord.end(), car_t::less_txy);
	  for (int i=0; i<ord.size(); i++)
	    sx[ord[i].id] = i;
	}
      }
	
    } else if (phase == PHASE_SORT) {
      int sorted = 0;
      int n = 0;
      for (int sort_y=1; sort_y<H; sort_y+=2) {
	int mx = -1;
	vector<int> mn(W);
	mn[W-1] = W;
	for (int x=W-1; x>=0; x--) {
	  if (cur[sort_y-1][x] >= 0)
	    mn[x] = min(mn[x], sx[cur[sort_y-1][x]]);
	  if (cur[sort_y][x] >= 0)
	    mn[x] = min(mn[x], sx[cur[sort_y][x]]);
	  if (x > 0)
	    mn[x-1] = mn[x];
	}

	for (int x=0; x<W; x++) {
	  int id;
	  id = cur[sort_y-1][x];
	  if (id > 0) {
	    n++;
	    if (x == sx[id])
	      move_or_stay(id, 'D', cars, cur, nxt, moves);
	    else
	      move_or_stay(id, 'L', cars, cur, nxt, moves);
	  }
	  id = cur[sort_y][x];
	  if (id > 0) {
	    n++;
	    if (sx[id] == mn[x]) {
	      if (sx[id] == cars[id].x) {
		sorted ++;
		move_or_stay(id, '-', cars, cur, nxt, moves);
	      } else {
		move_or_stay(id, 'U', cars, cur, nxt, moves);
	      }
	    } else {
	      move_or_stay(id, 'R', cars, cur, nxt, moves);
	    }
	  }
	}
      }
      for (int i=0; i<K; i++)
	if (moves[i] == '*') 
	  move_or_stay(i, '-', cars, cur, nxt, moves);

      bool frozen = true;
      for (int i=0; frozen && i<K; i++)
	if (moves[i] != '-')
	  frozen = false;

      cerr << "so: " << sorted << "/" << n << endl;
      if (sorted == n || frozen) {
	phase = PHASE_UP;
      }
    } else if (phase == PHASE_UP) {
      for (int id=0; id<K; id++)
	move_or_stay(id, 'U', cars, cur, nxt, moves);
      int c = 0;
      for (int id=0; id<K; id++)
	if (cars[id].y < target_y-2)
	  c++;
      if (c == K)
	phase = PHASE_MID;
    } if (phase == PHASE_MID) {
      int c = 0;
      int n = 0;
      for (int x=0; x<W; x+=3) {
	int qy = -1;
	for (int y=0; y<target_y-2; y++)
	  for (int dx=0; dx<3; dx++) {
	    int id = cur[y][x+dx];
	    if (id >= 0 && my[id] > qy)
	      qy = my[id];
	  }
	    
	for (int y=0; y<H; y++) {
	  for (int dx=0; dx<3; dx++) {
	    int id = cur[y][x+dx];
	    if (id < 0)
	      continue;

	    if (my[id] >= target_y) {
	      n++;
	      if (cars[id].x == mx[id] && cars[id].y > my[id]) {
		c++;
		move_or_stay(id, 'U', cars, cur, nxt, moves);
	      } else if (cars[id].x == mx[id] && cars[id].y == my[id]) {
		c++;
		move_or_stay(id, '-', cars, cur, nxt, moves);
	      } else if (cars[id].y >= target_y-2 && cars[id].x == mx[id]) {
		c++;
		move_or_stay(id, 'D', cars, cur, nxt, moves);	      
	      } else if (cars[id].y == target_y-1 && cars[id].x < mx[id])
		move_or_stay(id, 'R', cars, cur, nxt, moves);	      
	      else if (cars[id].y == target_y-2 && cars[id].x > mx[id])
		move_or_stay(id, 'L', cars, cur, nxt, moves);
	      else if (cars[id].y >= target_y-1 && cars[id].x != mx[id])
		move_or_stay(id, 'U', cars, cur, nxt, moves);
	      else {
		move_or_stay(id, "RDL"[dx], cars, cur, nxt, moves);
	      }
	    } else if (t > 10 && my[id] == qy) {
	      if (cars[id].y < qy-4)
		move_or_stay(id, "RDL"[dx], cars, cur, nxt, moves);
	      else
		move_or_stay(id, "R-L"[dx], cars, cur, nxt, moves);
	    }
	  }
	  
	  if (cur[y][x+1] >= 0) {
	    if (cars[cur[y][x+1]].x > cars[cur[y][x+1]].tx)
	      move_if_possible(cur[y][x+1], 'L', cars, cur, nxt, moves);
	    move_if_possible(cur[y][x+1], 'R', cars, cur, nxt, moves);
	    move_if_possible(cur[y][x+1], 'L', cars, cur, nxt, moves);
	  }
	  move_or_stay(cur[y][x+1], 'D', cars, cur, nxt, moves);
	  move_if_possible(cur[y][x], 'U', cars, cur, nxt, moves);
	  if (cur[y][x] >= 0 && y%2 == 0)
	    move_or_stay(cur[y][x], 'L', cars, cur, nxt, moves);
	  else
	    move_or_stay(cur[y][x], 'U', cars, cur, nxt, moves);
	  move_if_possible(cur[y][x+2], 'U', cars, cur, nxt, moves);
	  if (cur[y][x+2] >= 0 && y%2 == 1)
	    move_or_stay(cur[y][x+2], 'R', cars, cur, nxt, moves);
	  else
	    move_or_stay(cur[y][x+2], 'U', cars, cur, nxt, moves);
	}
      }
      if (c == K) {
	phase = PHASE_FINISH;
      } else if (c == n) {
	target_y --;
      }
    } else if (phase == PHASE_FINISH) {
      int c = 0;
      for (int y=0; y<H; y++)
	for (int x=0; x<W; x++) {
	  int id = cur[y][x];
	  if (id >= 0) {
	    if (cars[id].finished()) {
	      move_or_stay(id, '-', cars, cur, nxt, moves);
	      c++;
	    } else if (cars[id].y < cars[id].ty) {
	      move_or_stay(id, 'D', cars, cur, nxt, moves);
	    } else {
	      move_or_stay(id, 'U', cars, cur, nxt, moves);
	    }
	  }
	}
      if (c == K)
	phase = PHASE_DONE;
    } else if (phase == PHASE_DONE) {
      break;
    }

    sol.push_back(moves);

    cur = nxt;
    for (auto& tmp : nxt) { fill(tmp.begin(), tmp.end(), -1); }

    double sc = score_function(t, cars);
    if (best_t < 0 || sc >= best_score) {
      cerr << "turn: " << t << " " << sc << endl;
      best_score = sc;
      best_t = t;
    }

  }

 finished:
  if (phase != PHASE_DONE)
    best_t = sol.size()-1;
  sol.resize(best_t+1);
  
  return sol;
}  

int main()
{
  cin >> H >> W >> K >> T;
  assert(H == 30);
  assert(W == 30);
  assert(K == 450);
  assert(T == 10000);
  vector<car_t> cars(K);
  for (int i=0; i<K; i++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    car_t car(i, a, b, c, d);
    cars[i] = car;
  }

  auto sol = solve_greedy(cars);
  cout << sol.size() << endl;
  for (int i=0; i<sol.size(); i++) {
    cout << sol[i] << endl;
  }
}

Submission

Task問題 B - 日本橋大渋滞
User nameユーザ名 yowa
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1000067
Source lengthソースコード長 21119 Byte
File nameファイル名
Exec time実行時間 19 ms
Memory usageメモリ使用量 896 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 34247 / 50000 subtask_01_01.txt
test_02 33157 / 50000 subtask_01_02.txt
test_03 32426 / 50000 subtask_01_03.txt
test_04 33423 / 50000 subtask_01_04.txt
test_05 33445 / 50000 subtask_01_05.txt
test_06 33245 / 50000 subtask_01_06.txt
test_07 33761 / 50000 subtask_01_07.txt
test_08 33761 / 50000 subtask_01_08.txt
test_09 33267 / 50000 subtask_01_09.txt
test_10 33378 / 50000 subtask_01_10.txt
test_11 33991 / 50000 subtask_01_11.txt
test_12 33356 / 50000 subtask_01_12.txt
test_13 33648 / 50000 subtask_01_13.txt
test_14 31888 / 50000 subtask_01_14.txt
test_15 32321 / 50000 subtask_01_15.txt
test_16 33603 / 50000 subtask_01_16.txt
test_17 33671 / 50000 subtask_01_17.txt
test_18 33047 / 50000 subtask_01_18.txt
test_19 33026 / 50000 subtask_01_19.txt
test_20 33558 / 50000 subtask_01_20.txt
test_21 33716 / 50000 subtask_01_21.txt
test_22 33580 / 50000 subtask_01_22.txt
test_23 33267 / 50000 subtask_01_23.txt
test_24 32321 / 50000 subtask_01_24.txt
test_25 33245 / 50000 subtask_01_25.txt
test_26 33830 / 50000 subtask_01_26.txt
test_27 34130 / 50000 subtask_01_27.txt
test_28 33267 / 50000 subtask_01_28.txt
test_29 33047 / 50000 subtask_01_29.txt
test_30 33445 / 50000 subtask_01_30.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 17 ms 768 KB
subtask_01_02.txt AC 18 ms 768 KB
subtask_01_03.txt AC 19 ms 768 KB
subtask_01_04.txt AC 18 ms 768 KB
subtask_01_05.txt AC 18 ms 768 KB
subtask_01_06.txt AC 18 ms 768 KB
subtask_01_07.txt AC 18 ms 768 KB
subtask_01_08.txt AC 17 ms 768 KB
subtask_01_09.txt AC 18 ms 768 KB
subtask_01_10.txt AC 18 ms 768 KB
subtask_01_11.txt AC 17 ms 768 KB
subtask_01_12.txt AC 18 ms 768 KB
subtask_01_13.txt AC 18 ms 768 KB
subtask_01_14.txt AC 19 ms 896 KB
subtask_01_15.txt AC 19 ms 768 KB
subtask_01_16.txt AC 18 ms 768 KB
subtask_01_17.txt AC 18 ms 768 KB
subtask_01_18.txt AC 18 ms 768 KB
subtask_01_19.txt AC 19 ms 768 KB
subtask_01_20.txt AC 18 ms 768 KB
subtask_01_21.txt AC 18 ms 768 KB
subtask_01_22.txt AC 18 ms 768 KB
subtask_01_23.txt AC 18 ms 768 KB
subtask_01_24.txt AC 18 ms 768 KB
subtask_01_25.txt AC 19 ms 768 KB
subtask_01_26.txt AC 17 ms 768 KB
subtask_01_27.txt AC 17 ms 768 KB
subtask_01_28.txt AC 18 ms 768 KB
subtask_01_29.txt AC 18 ms 768 KB
subtask_01_30.txt AC 18 ms 768 KB