Submission #1173525

---

Source Code Expand

#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_txy(const car_t& a,const car_t& b) {
    return (a.ty != b.ty) ? (a.ty < b.ty) : (a.tx < b.tx);
  }
};
ostream& operator<<(ostream& os,const car_t& car) {
  os << "#" << car.id << "(" << car.x << " " << car.y << ")";
  return os;
}

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);
}

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));
  for (const auto car: cars) {
    cur[car.y][car.x] = car.id;
  }    

  auto us(cars);
  sort(us.begin(), us.end(), car_t::less_txy);
  cerr << cars[0] << endl;

  vector<string> sol;
  xor128_t rng;
  int best_t = -1;
  double best_score = 0;
  for (int t=0; t<T; t++) {
    {
      for (const auto& car : cars) {
	if (cur[car.y][car.x] != car.id)
	  cerr << car << " " << cur[car.y][car.x] << endl;
      }
      for (const auto& car : cars) {
	assert(cur[car.y][car.x] == car.id);
      }
    }
    string moves(K, '*');
    for (auto& car : cars) {
      if (false && car.finished()) {
	moves[car.id] = '-';
	nxt[car.y][car.x] = car.id;
	continue;
      }

      for (int i=0; i<5; i++) {
	int q = i;

	if (q == 0 && car.x < W-1 && cur[car.y][car.x+1] < 0 && nxt[car.y][car.x+1] < 0 && (car.x < car.tx || rng.get(8) == 0)) {
	  car.x ++;
	  moves[car.id] = 'R';
	  nxt[car.y][car.x] = car.id;
	  break;
	} else if (q == 1 && car.y > 0 && cur[car.y-1][car.x] < 0 && nxt[car.y-1][car.x] < 0 && (car.y > car.ty || rng.get(8) == 0)) {
	  car.y --;
	  moves[car.id] = 'U';
	  nxt[car.y][car.x] = car.id;
	  break;
	} else if (q == 2 && car.x > 0 && cur[car.y][car.x-1] < 0 && nxt[car.y][car.x-1] < 0 && (car.x > car.tx || rng.get(8) == 0)) {
	  car.x --;
	  moves[car.id] = 'L';
	  nxt[car.y][car.x] = car.id;
	  break;
	} else if (q == 3 && car.y < H-1 && cur[car.y+1][car.x] < 0 && nxt[car.y+1][car.x] < 0 && (car.y < car.ty || rng.get(8) == 0)) {
	  car.y ++;
	  moves[car.id] = 'D';
	  nxt[car.y][car.x] = car.id;
	  break;
	} else if (q == 4) {
	  moves[car.id] = '-';
	  nxt[car.y][car.x] = car.id;
	  break;
	}
      }
      assert(moves[car.id] != '*');
    }

    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;
    }
  }
 fail:
  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 (const auto& s : sol)
    cout << s << endl;
}

Submission Info

Judge Result