Submission #2201609

---

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 HERE (cerr << "LINE: " << __LINE__ << " " << __FUNCTION__ << endl)

typedef long long ll_t;
typedef unsigned long long ull_t;

#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;
}
template<typename T>
void assign_min_max(T& min,T& max,const T& x) {
  if (x < min)
    min = x;
  if (x > max)
    max = x;
}
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);
}
uint64_t hash_function64(uint64_t p) {
  // xor64()
  p ^= p<<16;
  p ^= p>>7;
  p ^= p<<39;
  uint64_t c = __builtin_popcount(p);
  return p<<c | p>>(64-c);
}  

struct xor128_t {
  uint64_t 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 uint64_t get() {
    uint64_t t=(x^(x<<11)); x=y; y=z; z=w;
    return (w=(w^(w>>19))^(t^(t>>8)));
  }

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

    uint64_t x;
    const uint64_t 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 int64_t 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]));
  }
};

struct reusable_set_t {
  typedef uint8_t mark_t;
  mark_t mark;
  vector<mark_t> v;
  reusable_set_t() {}
  reusable_set_t(int n) : v(n), mark(1) {}

  void insert(int x) { v[x] = mark; }
  void erase(int x) { v[x] = mark-1; }
  int count(int x) const { return (v[x] == mark); }
  void clear() {
    mark++;
    if (mark == 0) {
      fill(v.begin(), v.end(), 0);
      mark ++;
    }
  }
};

struct sa_t {
  double ini, fin, inv_T, progress;
  int num_call, num_accept, num_better;
  xor128_t rng;
  sa_t() {}
  sa_t(double ini, double fin) : ini(ini), fin(fin), num_accept(0), num_call(0), num_better(0) {
    set_progress(0);
  }

  void set_progress(double x) {
    progress = clamp(x, 0.0, 1.0);
    inv_T = 1 / (ini * pow(fin/ini, progress));
  }

  bool acceptable(double x) {
    //bool result = (x > 0) || rng.get_double() < exp(x*inv_T);
    //bool result = (x > 0) || log(1-rng.get_double()) < x*inv_T;
    double z = x*inv_T;
    bool result = (x > 0) || (z > -12 && log(1-rng.get_double()) < z);

    //num_call ++;
    //num_accept += result;
    //num_better += (x > 0);

    return result;
  }

  void show_log() const {
    cerr << "better/accept/call: "
	 << num_better
	 << "/" << num_accept
	 << "/" << num_call 
	 << " " << (double)num_accept/num_call << endl;
  }
};

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 * 10.0;

int N, K;
const int W = 64;
int CP(int x,int y) { return (y+1)*W+(x+1); }
int CX(int p) { return p%W - 1; }
int CY(int p) { return p/W - 1; }

struct field_t {
  vector<int> f, dmp;
  field_t() {
    f.resize((N+2)*W);
  }

  int score(vector<pair<int,int>>& fs) {
    return 0;
  }
};

int pri(int p) {
  int x = CX(p);
  int y = CY(p);
  return -(10000*abs(x+y-N) + ((x+y)%2*2-1)*(x-y));
}

vector<int> distance_map(const vector<int8_t>& f, int s) {
  vector<int> dmp(W*W, 2*W*W);

  vector<int> que, que2;
  que.push_back(s);
  for (int d=0; !que.empty(); d++) {
    que2.clear();
    for (const auto p : que) {
      if (dmp[p] <= d)
	continue;
      dmp[p] = d;
      
      for (int d : {1, -1, W, -W}) {
	int q = p + d;
	if (f[q] || dmp[q] < d+1)
	  continue;
	que2.push_back(q);
      }
    }
    que.swap(que2);
  }

  return dmp;
}

int rough_distance(int a, int b,int w,int len) {
  // wall
  if (a > len || b > len || a == w || b == w)
    return 0;
  if (a > b)
    swap(a, b);
  
  if (w < 0) {
    int d = abs(a - b);
    return min(d, len-d);
  } else {
    int d = abs(a - b);
    if (w > a && w < b) {
      return len - d;
    } else {
      return d;
    }	    
  }
}

vector<int> make_plan(vector<int8_t> f, int initial_turn, const vector<pair<int,int>>& routes) {
  auto dmp = distance_map(f, CP(0, N-2));
  f[CP(0, N-1)] = 0;
  int len = dmp[CP(0, N-1)] = dmp[CP(1, N-1)] + 1;
  len++;
#if 0  
  for (int y=0; y<N; y++) {
    for (int x=0; x<N; x++)
      fprintf(stderr, "%04d ", dmp[CP(x, y)]);
    fprintf(stderr, "\n");
  }
#endif

  set<int> bad_walls;
  for (int y=0; y<N; y++)
    for (int x=0; x<N; x++) {
      int p = CP(x, y);
      if (!f[p]) {
	int cnt = f[p-1] + f[p+1] + f[p-W] + f[p+W];
	if (cnt <= 1) {
	  //cerr << x << "," << y << " " << dmp[p] << endl;
	  bad_walls.insert(dmp[p]);
	}
      }
    }

  map<int,pair<int,vector<int>>> que, que2;
  que[dmp[CP(0, N-1)]] = make_pair(0, vector<int>());
  for (int t=initial_turn; t<routes.size(); t++) {
    que2.clear();
    int a, b;
    tie(a, b) = routes[t];
    map<int,pair<int,int>> cands;
    vector<int> rev;
    int best = 0;
    for (const auto& pa : que) {
      int w = pa.first;
      int sc = pa.second.first;
      if (sc > best) {
	best = sc;
	//cerr << t << ":" << pa.second.first << endl;
      }
      if (w < 0) {
	for (int w2=-1; w2<len; w2++) {
	  if (bad_walls.count(w2))
	    continue;
	  int d = rough_distance(dmp[a], dmp[b], w2, len);
	  int sc2 = sc + d*d;
	  if (!cands.count(w2) || cands[w2].first <= sc2) {
	    cands[w2] = make_pair(sc2, w);
	  }
	}
      } else {
	for (int w2 : {-1, w}) {
	  int d = rough_distance(dmp[a], dmp[b], w2, len);
	  int sc2 = sc + d*d;
	  if (!cands.count(w2) || cands[w2].first <= sc2) {
	    cands[w2] = make_pair(sc2, w);
	  }
	}
      }
    }
    for (const auto& pa : cands) {
      auto v(que[pa.second.second].second);
      v.push_back(pa.first);
      que2[pa.first] = make_pair(pa.second.first, v);
    }
    
    que.swap(que2);
  }
  int best_i = -1;
  for (const auto& pa : que) {
    if (pa.second.first > que[best_i].first)
      best_i = pa.first;
  }
  vector<int> plan;
  map<int,int> rev;
  for (int y=0; y<N; y++)
    for (int x=0; x<N; x++) {
      int p = CP(x, y);
      rev[dmp[p]] = p;
    }

  const auto& v(que[best_i].second);
  int cur = dmp[CP(0, N-1)];
  for (int i=0; i<v.size(); i++) {
    int p = -1;
    if (v[i] == cur) {
      p = -1;
    } else if (v[i] == -1) {
      p = cur;
      cur = -1;
    } else if (cur == -1) {
      cur = p = v[i];
    } else {
      assert(false);
    }

    plan.push_back((p == -1) ? CP(-1, -1) : rev[p]);
  }

  return plan;
}

int distance(const vector<int8_t>& f, int s, int g) {
  vector<int> dmp(W*W, 2*W*W);

  vector<int> que, que2;
  que.push_back(s);
  for (int d=0; !que.empty(); d++) {
    que2.clear();
    for (const auto p : que) {
      if (p == g)
	return d;
      
      if (dmp[p] <= d)
	continue;
      dmp[p] = d;
      
      for (int d : {1, -1, W, -W}) {
	int q = p + d;
	if (f[q] || dmp[q] < d+1)
	  continue;
	que2.push_back(q);
      }
    }
    que.swap(que2);
  }

  return -1;
}

vector<int> solve(vector<pair<int,int>>& fs) {
  vector<int> sol;
  vector<int8_t> f(W*W, 1);
  for (int y=0; y<N; y++)
    for (int x=0; x<N; x++)
      f[CP(x, y)] = 0;

  priority_queue<pair<int,int>> cands;
  for (int u=0; u<2*N+3; u++) {
    int s = (u%2) ? N+2+(u/2)*3 : N-1-(u/2)*3;
    
    for (int y=0; y<N; y++) {
      int x = s-y;
      if (x >= 2 && x < N && y >= 0 && y < N-2 &&
	  ((u%4==1 || u%4==2) ? (x > 2 && y < N-3) : (y > 0 && x < N-1))) {
	int p = CP(x, y);
	cands.emplace(pri(p), p);
      }
    }
  }
  for (int u=1; u<N-1; u++) {
    int v;
    int c = 0;
    if (u%6 == 1) {
      continue;
    } else if (u%6 == 2) {
      v = 0;
      c = -999999;
    } else if (u%6 == 3) {
      v = 2;
    } else {
      v = 1;
    }

    int p;
    p = CP(u+1, N-1-v);
    cands.emplace((c) ? c : pri(p), p);
    p = CP(v, N-2-u);
    cands.emplace((c) ? c : pri(p), p);
  }

  cands.emplace(123456789, CP(0, N-1));
  cands.emplace(123456789, CP(1, N-2));

  int stopper = CP(0, N-1);
  vector<int> plan;

  for (int i=0; i<K; i++) {
    int p = CP(-1, -1);

    int a, b;
    tie(a, b) = fs[i];

    if (cands.empty() && plan.empty()) {
      plan = make_plan(f, i, fs);
    }

    if (!plan.empty()) {
      p = plan.front();
      plan.erase(plan.begin());
      if (!cands.empty()) {
	p = cands.top().second;
	cands.pop();
      } if (p == CP(-1, -1) && plan[0] == CP(-1, -1)) {
	if (f[a]^f[b]) {
	  int c = (f[a]) ? a : b;
	  p = c;
	  cands.emplace(0, c);
	}
      }
    } else if (!cands.empty()) {
      p = cands.top().second;
      cands.pop();
    } 

    f[p] ^= 1;
    sol.push_back(p);
  }

  return sol;
}

int main()
{
  cin >> N >> K;
  vector<pair<int,int>> fs;
  for (int i=0; i<K; i++) {
    int y0, x0, y1, x1;
    cin >> y0 >> x0 >> y1 >> x1;
    fs.push_back(make_pair(CP(x0, y0), CP(x1, y1)));
  }

  auto ret = solve(fs);

  for (int i=0; i<ret.size(); i++)
    cout << CY(ret[i]) << " " << CX(ret[i]) << endl;
}

Submission Info

Judge Result