Submission #669846

---

Source Code Expand

#ifndef KOMAKI_LOCAL
//#define NDEBUG
#endif

#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64         int64_t
#define rep(i, n)   for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v)       ((i64)((v).size()))
#define bit(n)      (((i64)1)<<((i64)(n)))
#define all(v)      (v).begin(), (v).end()

std::string dbgDelim(int &i){ return (i++ == 0 ? "" : ", "); }
#define dbgEmbrace(exp) { int i = 0; os << "{"; { exp; } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q);
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp);
template <int INDEX, class TUPLE> void dbgDeploy(std::ostream &os, TUPLE tuple){}
template <int INDEX, class TUPLE, class H, class ...Ts> void dbgDeploy(std::ostream &os, TUPLE t)
{ os << (INDEX == 0 ? "" : ", ") << get<INDEX>(t); dbgDeploy<INDEX + 1, TUPLE, Ts...>(os, t); }
template <class T, class K> void dbgDeploy(std::ostream &os, std::pair<T, K> p, std::string delim)
{ os << "(" << p.first << delim << p.second << ")"; }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, std::tuple<Ts...> t)
{ os << "("; dbgDeploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p)
{ dbgDeploy(os, p, ", "); return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v)
{ dbgEmbrace( for(T t: v){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> s)
{ dbgEmbrace( for(T t: s){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.front(); }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.top();   }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
#define DBG_OUT std::cerr
#define DBG_OVERLOAD(_1, _2, _3, _4, _5, _6, macro_name, ...) macro_name
#define DBG_LINE() { char s[99]; sprintf(s, "line:%3d | ", __LINE__); DBG_OUT << s; }
#define DBG_OUTPUT(v) { DBG_OUT << (#v) << "=" << (v); }
#define DBG1(v, ...) { DBG_OUTPUT(v); }
#define DBG2(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG1(__VA_ARGS__); }
#define DBG3(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG2(__VA_ARGS__); }
#define DBG4(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG3(__VA_ARGS__); }
#define DBG5(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG4(__VA_ARGS__); }
#define DBG6(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG5(__VA_ARGS__); }

#define DEBUG0() { DBG_LINE(); DBG_OUT << std::endl; }
#define DEBUG(...)                                                      \
  {                                                                     \
    DBG_LINE();                                                         \
    DBG_OVERLOAD(__VA_ARGS__, DBG6, DBG5, DBG4, DBG3, DBG2, DBG1)(__VA_ARGS__); \
    DBG_OUT << std::endl;                                               \
  }


class Timer
{
public:
  void restart();
  double getElapsed();

  Timer();
private:
  static double rdtsc_per_sec_inv;

  double getTimeOfDay();
  unsigned long long int getCycle();

  double start_time;
  unsigned long long int start_clock;
};
double Timer::rdtsc_per_sec_inv = -1;


inline double Timer::getElapsed()
{
  if(rdtsc_per_sec_inv != -1) return (double)(getCycle() - start_clock) * rdtsc_per_sec_inv;

  const double RDTSC_MEASUREMENT_INTERVAL = 0.1;
  double res = getTimeOfDay() - start_time;
  if(res <= RDTSC_MEASUREMENT_INTERVAL) return res;

  rdtsc_per_sec_inv = 1.0 / (getCycle() - start_clock);
  rdtsc_per_sec_inv *= getTimeOfDay() - start_time;
  return getElapsed();
}

inline void Timer::restart()
{
  start_time = getTimeOfDay();
  start_clock = getCycle();
}

Timer::Timer()
{
  restart();
}

inline double Timer::getTimeOfDay()
{
  timeval tv;
  gettimeofday(&tv,0);
  return tv.tv_sec + tv.tv_usec * 0.000001;
}

inline unsigned long long int Timer::getCycle()
{
  unsigned int low, high;
  __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
  return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}


Timer global_timer;


//#define LOCAL


#ifdef LOCAL
const i64 N = 30;
#else
const i64 N = 30;
#endif
const i64 H = 105;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int heights[N][N];
int up[N][N][H];
int down[N][N][H];


class Pos
{
public:
  Pos(int x, int y, int h) : x(x), y(y), h(h) {}
  int getIndex(){ return (h << 12) | (y << 6) | x; }
  int x, y, h;
};

class Path
{
public:
  Path(vector<Pos> positions) : positions(positions) {}
  vector<Pos> positions;
  int min_timestamp;
  int max_timestamp;
};

vector<Path> greedy(bool shuffle_dirs=true)
{
  //srand(time(NULL));
  int t[N][N];
  rep(x, N)rep(y, N) t[x][y] = heights[x][y];


  vector<int> first_dirs = {0, 1, 2, 3};
  vector<int> second_dirs = {3, 2, 1, 0};
  if(shuffle_dirs){
    random_shuffle(all(first_dirs));
    random_shuffle(all(second_dirs));
  }

  vector<Path> paths;
  while(true){
    vector<pair<int, int>> survivers;
    for(int x = 0; x < N; ++x){
      for(int y = 0; y < N; ++y){
        if(0 < t[x][y]) survivers.push_back(make_pair(x, y));
      }
    }
    if(sz(survivers) == 0) break;
    swap(survivers[0], survivers[rand() % sz(survivers)]);
    rep(step, 3){
      int i = rand() % sz(survivers);
      int h0 = t[survivers[0].first][survivers[0].second];
      int h1 = t[survivers[i].first][survivers[i].second];
      if(h0 > h1) swap(survivers[0], survivers[i]);
    }

    int cx = survivers[0].first;
    int cy = survivers[0].second;
    while(true){
      vector<int> dirs = first_dirs;
      if(rand() % 2) random_shuffle(all(dirs));
      int dir = -1;
      rep(i, sz(dirs)){
        int nx = cx + dx[dirs[i]];
        int ny = cy + dy[dirs[i]];
        if(nx < 0 || N <= nx) continue;
        if(ny < 0 || N <= ny) continue;
        if(t[nx][ny] <= t[cx][cy]) continue;
        cx = nx;
        cy = ny;
        dir = dirs[i];
        break;
      }
      if(dir == -1) break;
    }
    int ch = t[cx][cy] - 1;
    vector<Pos> positions;
    set<pair<int, int>> used;
    while(true){
      --t[cx][cy];
      positions.push_back(Pos(cx, cy, ch--));
      used.insert(make_pair(cx, cy));

      vector<int> dirs = second_dirs;
      int dir = -1;
      rep(i, sz(dirs)){
        int nx = cx + dx[dirs[i]];
        int ny = cy + dy[dirs[i]];
        if(nx < 0 || N <= nx) continue;
        if(ny < 0 || N <= ny) continue;
        if(t[nx][ny] != t[cx][cy] || t[nx][ny] == 0) continue;
        if(used.count(make_pair(nx, ny))) continue;
        cx = nx;
        cy = ny;
        dir = dirs[i];
        break;
      }
      if(dir == -1) break;
    }
    paths.push_back(Path(positions));
  }
  return paths;
}

void setTimestamp(vector<Path> &paths)
{
  unordered_map<int, int> pos_to_path_index;
  vector<int> dependencies;
  vector<int> ready;

  for(Path &path: paths){
    for(Pos &pos: path.positions){
      pos_to_path_index[pos.getIndex()] = sz(dependencies);
    }
    dependencies.push_back(sz(path.positions));
  }

  rep(x, N)rep(y, N){
      int index = pos_to_path_index[Pos(x, y, heights[x][y] - 1).getIndex()];
      if(--dependencies[index] == 0) ready.push_back(index);
    }

  int timestamp = 0;
  while(sz(ready)){
    swap(ready.back(), ready[rand() % sz(ready)]);
    int index = ready.back();
    ready.pop_back();
    paths[index].min_timestamp = timestamp;
    paths[index].max_timestamp = timestamp;
    ++timestamp;

    for(Pos &pos: paths[index].positions){
      if(pos.h == 0) continue;
      int i = pos_to_path_index[Pos(pos.x, pos.y, pos.h - 1).getIndex()];
      if(--dependencies[i] == 0) ready.push_back(i);
    }
  }
  rep(i, sz(dependencies)){
    if(dependencies[i] == 0) continue;
    for(Pos &pos : paths[i].positions){
    }
  }
  assert(sz(paths) == timestamp);
}

void print(vector<Path> &paths)
{
  setTimestamp(paths);
  vector<pair<int, Path*>> sorted;
  for(Path &path: paths) sorted.push_back(make_pair(path.min_timestamp, &path));
  sort(all(sorted));
#ifdef LOCAL
  DEBUG(sz(sorted));
#endif
  for(pair<int, Path*> &path: sorted){
    for(Pos &pos: path.second->positions){
#ifndef LOCAL
      cout << pos.x + 1 << " " << pos.y + 1 << endl;
#endif
    }
  }
}

class Edge
{
public:
  Edge() {}
  Edge(int drop, int up, int down) : drop(drop), up(up), down(down) {}
  int drop, up, down;
};
int visited_timestamp = 100;
int visited_dat[H << 12];
int reachability_dat[H << 12];
Edge graph_edges[H << 12];

bool checkReachability(int source, int sink)
{
  int timestamp = ++visited_timestamp;
  int *visited = visited_dat;
  visited[source] = timestamp;

  int *head = reachability_dat;
  int *end = reachability_dat;
  *(end++) = source;

  while(head != end){
    int pos = *(--end);

    Edge &edge = graph_edges[pos];
    {
      int next = edge.up;
      if(next != -1){
        if(next == sink) return true;
        if(visited[next] != timestamp){
          visited[next] = timestamp;
          *(end++) = next;
        }
      }
    }
    {
      int next = edge.down;
      if(next != -1){
        if(next == sink) return true;
        if(visited[next] != timestamp){
          visited[next] = timestamp;
          *(end++) = next;
        }
      }
    }
    {
      int next = edge.drop;
      if(next != -1){
        if(next == sink) return true;
        if(visited[next] != timestamp){
          visited[next] = timestamp;
          *(end++) = next;
        }
      }
    }
  }
  return false;
}


vector<Path> connect(vector<Path> paths)
{
  if(1){
    vector<Path> dat = paths;
    vector<pair<pair<int, pair<int, int>>, int>> v;
    rep(i, sz(paths)) v.push_back(make_pair(make_pair(paths[i].positions.back().x, make_pair(paths[i].positions.back().y, paths[i].positions.back().h)), i));
    sort(all(v));
    if(rand() % 2) reverse(all(v));
    paths.clear();
    rep(i, sz(v)) paths.push_back(dat[v[i].second]);
  }



  unordered_map<int, int> top_pos_owner;
  rep(i, sz(paths)) top_pos_owner[paths[i].positions[0].getIndex()] = i;

  rep(x, N)rep(y, N) graph_edges[Pos(x, y, heights[x][y] - 1).getIndex()] = Edge(-1, -1, -1);
  rep(x, N)rep(y, N)rep(h, heights[x][y] - 1) graph_edges[Pos(x, y, h + 1).getIndex()] = Edge(Pos(x, y, h).getIndex(), -1, -1);
  for(Path &path0: paths){
    rep(i, sz(path0.positions) - 1){
      graph_edges[path0.positions[i + 0].getIndex()].down = path0.positions[i + 1].getIndex();
      graph_edges[path0.positions[i + 1].getIndex()].up   = path0.positions[i + 0].getIndex();
    }
  }

  //DEBUG(global_timer.getElapsed());
  int cnt = 0;
  for(Path &path0: paths){
    if(sz(path0.positions) == 0) continue;
    while(true){
      bool found = false;
      vector<int> dirs = {3, 2, 1, 0};
      //random_shuffle(all(dirs));
      rep(_dir, 4){
        int dir = dirs[_dir];
        Pos pos = path0.positions.back();
        int nx = pos.x + dx[dir];
        int ny = pos.y + dy[dir];
        if(nx < 0 || N <= nx) continue;
        if(ny < 0 || N <= ny) continue;
        if(pos.h == 0) continue;

        int index = Pos(nx, ny, pos.h - 1).getIndex();
        if(top_pos_owner.count(index) == 0 ) continue;

        int pi = top_pos_owner[index];
        if(pi == -1) continue;
        if(checkReachability(index, pos.getIndex())) continue;
        if(checkReachability(pos.getIndex(), index)) continue;

        top_pos_owner[index] = -1;

        graph_edges[pos.getIndex()].down = index;
        graph_edges[index].up = pos.getIndex();

        for(Pos &p: paths[pi].positions){
          path0.positions.push_back(p);
        }
        paths[pi].positions.clear();

        path0.max_timestamp = max(path0.max_timestamp, paths[pi].max_timestamp);
        path0.min_timestamp = min(path0.min_timestamp, paths[pi].min_timestamp);

        found = true;
        ++cnt;
      }
      if(!found) break;
      for(Pos &p: path0.positions){
        //cout << p.x << ", " << p.y << ", " << p.h << endl;
      }
    }
    //if(3000 < cnt) break;
  }
  //DEBUG(global_timer.getElapsed());

  vector<Path> res;
  for(Path &path: paths){
    if(sz(path.positions)) res.push_back(path);
  }

#ifdef LOCAL
  DEBUG(cnt);
  DEBUG(sz(res), sz(paths));
#endif

  return res;
}



/*

vector<Path> connect(vector<Path> paths)
{
  unordered_map<int, int> top_pos_owner;
  rep(i, sz(paths)) top_pos_owner[paths[i].positions[0].getIndex()] = i;

  int cnt = 0;
  for(Path &path0: paths){
    if(sz(path0.positions) == 0) continue;
    while(true){
      bool found = false;
      rep(dir, 4){
        Pos pos = path0.positions.back();
        int nx = pos.x + dx[dir];
        int ny = pos.y + dy[dir];
        if(nx < 0 || N <= nx) continue;
        if(ny < 0 || N <= ny) continue;
        if(pos.h == 0) continue;

        int index = Pos(nx, ny, pos.h - 1).getIndex();
        if(top_pos_owner.count(index) == 0 ) continue;

        int pi = top_pos_owner[index];
        if(pi == -1) continue;
        if(!(paths[pi].max_timestamp < path0.min_timestamp)) continue;
        top_pos_owner[index] = -1;

        for(Pos &p: paths[pi].positions){
          path0.positions.push_back(p);
        }
        paths[pi].positions.clear();

        path0.max_timestamp = max(path0.max_timestamp, paths[pi].max_timestamp);
        path0.min_timestamp = min(path0.min_timestamp, paths[pi].min_timestamp);

        found = true;
        ++cnt;
#ifdef LOCAL
        DEBUG(cnt);
#endif
      }
      if(!found) break;
      for(Pos &p: path0.positions){
        cout << p.x << ", " << p.y << ", " << p.h << endl;
      }
    }
    if(3 < cnt) break;
  }

  vector<Path> res;
  for(Path &path: paths){
    if(sz(path.positions)) res.push_back(path);
  }

#ifdef LOCAL
  DEBUG(cnt);
  DEBUG(sz(res), sz(paths));
#endif

  return res;
}

*/


inline int getIndex(int x, int y)
{
  return x * N + y;
}

inline double drand()
{
  return rand() % 1000000 / 1000000.0;
}

/*

void solve0()
{
  rep(x, N)rep(y, N)rep(h, H) up[x][y][h] = down[x][y][h] = -1;
  //rep(x, N)rep(y, N)rep(h, height[x][y]) cout << x + 1 << " " << y + 1 << endl;
  //return;

  int current_score = 0;
  rep(x, N)rep(y, N) current_score += heights[x][y];
  int best_score = current_score;

  const int dx[] = {1, 0, -1, 0};
  const int dy[] = {0, 1, 0, -1};
  while(global_timer.getElapsed() <= 1.5){
    int cx = rand() % N;
    int cy = rand() % N;
    int ch = rand() % heights[cx][cy];
    int nd = rand() % 4;
    int nx = cx + dx[nd];
    int ny = cy + dy[nd];
    if(nx < 0 || N <= nx) continue;
    if(ny < 0 || N <= ny) continue;
    if(down[cx][cy][ch] == nd) continue;

    int nh = ch - 1;
    if(nh < 0 || heights[nx][ny] <= nh) continue;
    int pd = down[cx][cy][ch];
    down[cx][cy][ch] = nd;

    bool ok = true;
    set<int> path;
    path.insert(getIndex(cx, cy));

    for(int x = cx, y = cy, h = ch; ok;){
      if(down[x][y][h] == -1) break;
      int xx = x + dx[down[x][y][h]];
      int yy = y + dy[down[x][y][h]];
      x = xx;
      y = yy;
      h = h - 1;
      if(path.count(getIndex(x, y))) ok = false;
      path.insert(getIndex(x, y));
    }
    for(int x = cx, y = cy, h = ch; ok;){
      if(up[x][y][h] == -1) break;
      int xx = x + dx[up[x][y][h]];
      int yy = y + dy[up[x][y][h]];
      x = xx;
      y = yy;
      h = h + 1;
      if(path.count(getIndex(x, y))) ok = false;
      path.insert(getIndex(x, y));
    }

    down[cx][cy][ch] = pd;
    if(!ok) continue;

    int score = 0;
    if(down[cx][cy][ch] == -1) score += 1;
    if(up[nx][ny][nh] != -1) score -= 1;

    if(score == 1){
      ok = true;
    }else if(score == 0){
      ok = false;//true;
    }else if(score == -1){
      ok = false;//drand() < 0.001;
    }else{
      assert(false);
    }
    if(!ok) continue;

    if(up[nx][ny][nh] != -1){
      int xx = nx + dx[up[nx][ny][nh]];
      int yy = ny + dy[up[nx][ny][nh]];
      down[xx][yy][ch] = -1;
    }
    if(down[cx][cy][ch] != -1){
      int xx = cx + dx[down[cx][cy][ch]];
      int yy = cy + dy[down[cx][cy][ch]];
      up[xx][yy][nh] = -1;
    }
    up[nx][ny][nh] = nd ^ 2;
    down[cx][cy][ch] = nd;

    current_score -= score;
    if(current_score < best_score){
      best_score = current_score;
#ifdef LOCAL
      cout << best_score << ", " << global_timer.getElapsed() << endl;
#endif
      break;
    }
  }

  {
    map<pair<pair<int, int>, int>, int> path_index;
    vector<vector<pair<pair<int, int>, int>>> paths;
    vector<int> dependencies;
    queue<int> ready;

    rep(x, N)rep(y, N)rep(h, heights[x][y]){
          if(up[x][y][h] != -1){
            continue;
          }
          vector<pair<pair<int, int>, int>> path;
          path.push_back(make_pair(make_pair(x, y), h));
          path_index[make_pair(make_pair(x, y), h)] = sz(paths);

          for(int xx = x, yy = y, hh = h; true;){
            if(down[xx][yy][hh] == -1) break;
            int xxx = xx + dx[down[xx][yy][hh]];
            int yyy = yy + dy[down[xx][yy][hh]];
            xx = xxx;
            yy = yyy;
            hh = hh - 1;
            path.push_back(make_pair(make_pair(xx, yy), hh));
            path_index[make_pair(make_pair(xx, yy), hh)] = sz(paths);
          }
          dependencies.push_back(sz(path));
          paths.push_back(path);
        }

    DEBUG0();
    rep(x, N)rep(y, N){
        int h = heights[x][y] - 1;
        int index = path_index[make_pair(make_pair(x, y), h)];
        if(--dependencies[index] == 0) ready.push(index);
      }
    DEBUG0();
    int debug_cnt = 0;
    while(sz(ready)){
      int index = ready.front();
      ready.pop();
      for(pair<pair<int, int>, int> pos: paths[index]){
        int x = pos.first.first;
        int y = pos.first.second;

#ifndef LOCAL
        cout << x + 1 << " " << y + 1 << endl;
#endif
        ++debug_cnt;

        int h = pos.second;
        if(h == 0) continue;
        int i = path_index[make_pair(make_pair(x, y), h - 1)];
        if(--dependencies[i] == 0) ready.push(i);
      }
    }
    int total_height = 0;
    rep(x, N)rep(y, N) total_height += heights[x][y];
    DEBUG(debug_cnt);
    DEBUG(total_height);
  }
}

*/

void test()
{
  cout << "start testing" << endl;
  exit(0);
}

void readInput()
{
  rep(i, N)rep(j, N) cin >> heights[i][j];
}

void randomInput()
{
  //srand(13521521);
  //srand(time(NULL));
  rep(i, N)rep(j, N) heights[i][j] = rand() % 100 + 1;
}

int main()
{
  // test();
  global_timer.restart();
#ifdef LOCAL
  int test_case = 1;
#else
  int test_case = 0;
#endif
  vector<vector<int>> mp;
  switch(test_case){
    case 0:
      readInput();
      break;
    case 1:
      randomInput();
      break;
    default:
      assert(false);
  }

  vector<Path> best_paths = greedy(false);
  best_paths = connect(best_paths);
  while(global_timer.getElapsed() < 7.5){
    vector<Path> paths = greedy();
    rep(i, 2){
      vector<Path> ps = greedy();
      if(sz(ps) < sz(paths)) paths = ps;
    }
    if(8.8 < global_timer.getElapsed()) break;
    paths = connect(paths);
    if(sz(paths) < sz(best_paths)){
      best_paths = paths;
    }
  }
  print(best_paths);
}

Submission Info

Judge Result