MM146 last submit

HappyGrid.cpp

// C++17
#include <cassert>
#include <cmath>
#include <chrono>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <climits>
#include <unordered_map>
#include <queue>
#include <set>
#include <cstring>
#include <vector>

using namespace std;
using namespace std::chrono;

typedef long long ll;
typedef pair<int, int> P;

const ll CYCLE_PER_SEC = 2700000000;
double TIME_LIMIT = 10.0;
double SA_TIME_LIMIT = TIME_LIMIT * 0.9;
double MST_TIME_LIMIT = TIME_LIMIT * 0.995;

unsigned long long xor128() {
  static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123;
  unsigned long long rt = (rx ^ (rx << 11));
  rx = ry;
  ry = rz;
  rz = rw;
  return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
}

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

double get_time(unsigned long long int begin_cycle) {
  return (double) (get_cycle() - begin_cycle) / CYCLE_PER_SEC;
}

double get_time(high_resolution_clock::time_point &begin) {
  high_resolution_clock::time_point end = high_resolution_clock::now();
  ll count = duration_cast<microseconds>(end - begin).count();

  return count / 1000000.0;
}

const char WALL = 0;
const int MAX_N = 30;
const int GRID_SIZE = MAX_N + 2;
const int DZ[5] = {-GRID_SIZE, 1, GRID_SIZE, -1, 0};
const int Z_MASK = 1023;
const ll CLEAR_MASK = 9223372036854774784LL;

ll g_visited[GRID_SIZE * GRID_SIZE];
ll g_vid;
int g_component_key[GRID_SIZE * GRID_SIZE];
int g_history[GRID_SIZE * GRID_SIZE];
int g_positions[GRID_SIZE * GRID_SIZE];
int g_target_positions[GRID_SIZE * GRID_SIZE];
char g_grid[GRID_SIZE * GRID_SIZE];
char g_target_grid[GRID_SIZE * GRID_SIZE];
char g_grid_origin[GRID_SIZE * GRID_SIZE];
vector<int> G[GRID_SIZE * GRID_SIZE];
int g_distance_penalty[GRID_SIZE * GRID_SIZE][GRID_SIZE * GRID_SIZE];

int N, C, K, BONUS;

int calc_z(int y, int x) {
  return y * GRID_SIZE + x;
}

struct Command {
  int key;

  Command(int key = -1) {
    this->key = key;
  }

  string to_s() {
    int from_z = key & Z_MASK;
    int to_z = (key >> 10) & Z_MASK;
    int from_y = from_z / GRID_SIZE;
    int from_x = from_z % GRID_SIZE;
    int to_y = to_z / GRID_SIZE;
    int to_x = to_z % GRID_SIZE;
    return to_string(from_y - 1) + " " + to_string(from_x - 1) + " " + to_string(to_y - 1) + " " + to_string(to_x - 1);
  }
};

struct PathNode {
  int z;
  int b_dir;
  int cost;

  PathNode(int z = -1, int b_dir = -1, int cost = -1) {
    this->z = z;
    this->b_dir = b_dir;
    this->cost = cost;
  }

  bool operator>(const PathNode &n) const {
    return cost > n.cost;
  }
};

struct Node {
  int z;
  int child_num;

  Node(int z = -1, int child_num = -1) {
    this->z = z;
    this->child_num = child_num;
  }

  bool operator>(const Node &n) const {
    if (child_num == n.child_num) {
      int y1 = z / GRID_SIZE;
      int x1 = z % GRID_SIZE;
      int y2 = n.z / GRID_SIZE;
      int x2 = n.z % GRID_SIZE;
      int d1 = abs(y1 - N / 2) + abs(x1 - N / 2);
      int d2 = abs(y2 - N / 2) + abs(x2 - N / 2);

      return d1 < d2;
    } else {
      return child_num > n.child_num;
    }
  }
};

struct Edge {
  int from;
  int to;
  int cost;

  Edge(int from = -1, int to = -1, int cost = 0) {
    this->from = from;
    this->to = to;
    this->cost = cost;
  }

  bool operator>(const Edge &e) const {
    if (cost == e.cost) {
      int y1 = from / GRID_SIZE;
      int x1 = from % GRID_SIZE;
      int y2 = e.from / GRID_SIZE;
      int x2 = e.from % GRID_SIZE;
      int dy1 = abs(y1 - N / 2);
      int dx1 = abs(x1 - N / 2);
      int dy2 = abs(y2 - N / 2);
      int dx2 = abs(x2 - N / 2);
      int d1 = dy1 + dx1;
      int d2 = dy2 + dx2;

      if (d1 == d2) {
        return max(dy1, dx1) > max(dy2, dx2);
      } else {
        return d1 > d2;
      }
    } else {
      return cost > e.cost;
    }
  }
};

class UnionFind {
public:
  vector<int> _parent;
  vector<int> _rank;
  vector<int> _size;

  UnionFind(int n) {
    for (int i = 0; i < n; ++i) {
      _parent.push_back(i);
      _rank.push_back(0);
      _size.push_back(1);
    }
  }

  int find(int x) {
    if (_parent[x] == x) {
      return x;
    } else {
      return _parent[x] = find(_parent[x]);
    }
  }

  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (_rank[x] < _rank[y]) {
      _parent[x] = y;
      _size[y] += _size[x];
    } else {
      _parent[y] = x;
      _size[x] += _size[y];
      if (_rank[x] == _rank[y]) ++_rank[x];
    }
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  int size(int x) {
    return _size[find(x)];
  }
};

class HappyGrid {
public:
  void load_data() {
    memset(g_component_key, 0, sizeof(g_component_key));
    memset(g_visited, 0, sizeof(g_visited));
    memset(g_grid, WALL, sizeof(g_grid));
    g_vid = 0;

    cin >> N >> C >> K >> BONUS;
    fprintf(stderr, "N = %d\n", N);
    fprintf(stderr, "C = %d\n", C);
    fprintf(stderr, "K = %d\n", K);
    fprintf(stderr, "P = %d\n", BONUS);

    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        char ch;
        cin >> ch;
        int color = ch - '0';
        g_grid[z] = color;
      }
    }

    memcpy(g_grid_origin, g_grid, sizeof(g_grid));
  }

  void setup() {
    setup_distance_penalty();
  }

  void setup_distance_penalty() {
    memset(g_distance_penalty, 0, sizeof(g_distance_penalty));

    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int cz = calc_z(y, x);
        if (g_grid[cz] == WALL) continue;

        queue <P> que;
        que.push(P(cz, 0));
        ++g_vid;

        while (not que.empty()) {
          P p = que.front();
          que.pop();
          int z = p.first;
          int dist = p.second;

          if (g_visited[z] == g_vid) continue;
          g_visited[z] = g_vid;
          g_distance_penalty[cz][z] = 2 * dist;

          for (int dir = 0; dir < 4; ++dir) {
            int nz = z + DZ[dir];
            if (g_grid[nz] == WALL) continue;

            que.push(P(nz, dist + 1));
          }
        }
      }
    }
  }

  vector <Command> build_commands(int min_size) {
    int cur_size = 0;
    vector <Command> commands(min_size + 1);
    bool reserved[GRID_SIZE * GRID_SIZE];
    memset(reserved, false, sizeof(reserved));
    memset(g_positions, -1, sizeof(g_positions));
    memcpy(g_grid, g_grid_origin, sizeof(g_grid_origin));

    priority_queue <Node, vector<Node>, greater<Node>> pque;

    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        g_positions[z] = z;
        if (g_grid[z] == WALL) continue;
        if (G[z].size() >= 2) continue;

        reserved[z] = true;
        pque.push(Node(z, G[z].size()));
      }
    }

    while (not pque.empty() && cur_size < min_size) {
      Node node = pque.top();
      pque.pop();

      if (g_grid[node.z] == WALL) continue;
      {
        int cz = find_path(node.z, g_target_grid[node.z], reserved);
        while (cz != node.z && cur_size < min_size) {
          int dir = g_history[cz] ^ 2;
          int nz = cz + DZ[dir];
          swap(g_grid[cz], g_grid[nz]);
          swap(g_positions[cz], g_positions[nz]);
          commands[cur_size] = Command((nz << 10) | cz);
          ++cur_size;
          cz = nz;
        }
        g_grid[node.z] = WALL;
      }

      for (int z : G[node.z]) {
        if (g_grid[z] == WALL) continue;

        int cnt = 0;
        for (int nz : G[z]) {
          if (g_grid[nz] != WALL) ++cnt;
        }
        if (cnt == 1) {
          reserved[z] = true;
          pque.push(Node(z, cnt));
        }
      }
    }

    memcpy(g_target_positions, g_positions, sizeof(g_positions));
    commands.resize(cur_size);

    return commands;
  }

  int find_path(int from, int color, bool *reserved) {
    if (g_grid[from] == color) return from;

    ++g_vid;
    priority_queue <PathNode, vector<PathNode>, greater<PathNode>> pque;
    pque.push(PathNode(from, -1, 0));

    while (not pque.empty()) {
      PathNode node = pque.top();
      pque.pop();
      int z = node.z;
      int b_dir = node.b_dir;

      if (g_visited[z] == g_vid) continue;
      g_visited[z] = g_vid;
      g_history[z] = b_dir;

      if (g_grid[z] == color) {
        return z;
      }

      for (int dir = 0; dir < 4; ++dir) {
        int nz = z + DZ[dir];
        if (g_grid[nz] == WALL) continue;
        if (g_visited[nz] == g_vid) continue;

        int id = g_positions[nz];
        int tz = g_target_positions[id];
        int d1 = g_distance_penalty[z][tz];
        int d2 = g_distance_penalty[nz][tz];

        int n_cost = node.cost + 100;
        if (d1 > d2) {
          n_cost += 50;
        }
        if (g_grid[nz] == g_target_grid[nz]) {
          n_cost += (reserved[nz]) ? 150 : 100;
        }
        if (g_grid[z] == g_target_grid[nz]) {
          n_cost -= (reserved[nz]) ? 150 : 100;
        }
        pque.push(PathNode(nz, dir, n_cost));
      }
    }

    assert(false);
    return 0;
  }

  int build_key(int z) {
    return (z << 10);
  }

  void build_mst() {
    memcpy(g_grid, g_grid_origin, sizeof(g_grid_origin));

    int V = xor128() % K + 2;
    priority_queue <Edge, vector<Edge>, greater<Edge>> pque;
    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        G[z].clear();
        if (g_grid[z] == WALL) continue;

        for (int dir = 0; dir < 2; ++dir) {
          int nz = z + DZ[dir];
          if (g_grid[nz] == WALL) continue;

          pque.push(Edge(z, nz, xor128() % V));
        }
      }
    }

    UnionFind uf(GRID_SIZE * GRID_SIZE);
    while (not pque.empty()) {
      Edge e = pque.top();
      pque.pop();

      if (uf.same(e.from, e.to)) continue;
      uf.unite(e.from, e.to);

      G[e.from].push_back(e.to);
      G[e.to].push_back(e.from);
    }
  }

  int init() {
    int score = 0;
    ++g_vid;

    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        if (g_grid[z] == WALL) continue;
        if (g_visited[z] == g_vid) continue;

        score += update_component(z);
      }
    }

    return score;
  }

  int calc_size_score(int k) {
    if (k == K) {
      return BONUS;
    } else if (abs(K - k) <= 1) {
      return BONUS / 8;
    } else {
      return -1 * abs(K - k);
    }
  }

  void search_best_grid(double time_limit = TIME_LIMIT) {
    ll start_cycle = get_cycle();
    int base_score = init();

    int positions[GRID_SIZE * GRID_SIZE];
    memset(positions, -1, sizeof(positions));

    vector<int> valid_positions[GRID_SIZE * GRID_SIZE];
    vector<int> all_positions;
    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        valid_positions[z].clear();
        positions[z] = z;
        if (g_grid[z] == WALL) continue;

        all_positions.push_back(z);

        for (int ny = 1; ny <= N; ++ny) {
          for (int nx = 1; nx <= N; ++nx) {
            int nz = calc_z(ny, nx);
            if (z == nz) continue;
            if (g_grid[nz] == WALL) continue;
            if (g_distance_penalty[z][nz] >= 10) continue;
            valid_positions[z].push_back(nz);
          }
        }
      }
    }
    int L = all_positions.size();

    int position_penalty = 0;
    int cur_score = base_score - position_penalty;
    int best_score = cur_score;
    char best_grid[GRID_SIZE * GRID_SIZE];
    memcpy(best_grid, g_grid, sizeof(g_grid));

    double cur_time = get_time(start_cycle);
    ll R = LLONG_MAX;
    int try_count = 0;
    int z1, z2;
    int temp_comp_key[GRID_SIZE * GRID_SIZE];
    memcpy(temp_comp_key, g_component_key, sizeof(g_component_key));
    const double T0 = BONUS * (0.5 - (C * K) * 0.005);
    double T = T0;

    while (cur_time < time_limit) {
      cur_time = get_time(start_cycle);
      double remain_time = (time_limit - cur_time) / time_limit;

      z1 = all_positions[xor128() % L];
      int id1 = positions[z1];
      do {
        z2 = valid_positions[id1][xor128() % valid_positions[id1].size()];
      } while (z1 == z2);

      int c1 = g_grid[z1];
      int c2 = g_grid[z2];
      int temp_position_penalty = position_penalty;

      int oz1 = positions[z1];
      int oz2 = positions[z2];
      position_penalty += (g_distance_penalty[oz1][z2] + g_distance_penalty[oz2][z1]) -
                          (g_distance_penalty[oz1][z1] + g_distance_penalty[oz2][z2]);

      int sub_score = 0;
      swap(positions[z1], positions[z2]);
      if (c1 != c2) {
        sub_score = swap_balls(z1, z2);
      }
      int score = cur_score + sub_score + (temp_position_penalty - position_penalty);
      double diff_score = score - cur_score;

      if (diff_score > 0 || (xor128() % R < R * exp(diff_score / T))) {
        cur_score = score;
        if (c1 != c2) {
          memcpy(temp_comp_key, g_component_key, sizeof(g_component_key));
        }

        if (best_score < score) {
          best_score = score;
          // fprintf(stderr, "%.4f: score: %d\n", remain_time, best_score);
          memcpy(best_grid, g_grid, sizeof(g_grid));
          memcpy(g_target_positions, positions, sizeof(positions));
        }
      } else {
        if (c1 != c2) {
          swap(g_grid[z1], g_grid[z2]);
          memcpy(g_component_key, temp_comp_key, sizeof(temp_comp_key));
        }
        swap(positions[z1], positions[z2]);
        position_penalty = temp_position_penalty;
      }


      ++try_count;
      if (try_count % 100 == 0) {
        double tt = 1.0 - remain_time;
        T = pow(T0, 1.0 - tt) * pow(tt, tt);
      }
    }

    int tp[GRID_SIZE * GRID_SIZE];
    memcpy(tp, g_target_positions, sizeof(g_target_positions));

    fprintf(stderr, "try_count: %d, best_score: %d\n", try_count, best_score);
    memcpy(g_grid, best_grid, sizeof(best_grid));
    memcpy(g_target_grid, best_grid, sizeof(best_grid));
    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        int id = tp[z];
        g_target_positions[id] = z;
      }
    }
  }

  int swap_balls(int z1, int z2) {
    int before_score = 0;
    int after_score = 0;
    int c1 = g_grid[z1];
    int c2 = g_grid[z2];

    before_score += clear_component(z1);
    before_score += clear_component(z2);

    for (int dir = 0; dir < 4; ++dir) {
      int nz = z1 + DZ[dir];
      if (g_grid[nz] != c2) continue;
      before_score += clear_component(nz);
    }
    for (int dir = 0; dir < 4; ++dir) {
      int nz = z2 + DZ[dir];
      if (g_grid[nz] != c1) continue;
      before_score += clear_component(nz);
    }

    swap(g_grid[z1], g_grid[z2]);

    ++g_vid;
    after_score += update_component(z1);
    after_score += update_component(z2);

    for (int dir = 0; dir < 4; ++dir) {
      int nz = z1 + DZ[dir];
      if (g_grid[nz] != c1) continue;
      if (g_visited[nz] == g_vid) continue;

      after_score += update_component(nz);
    }

    for (int dir = 0; dir < 4; ++dir) {
      int nz = z2 + DZ[dir];
      if (g_grid[nz] != c2) continue;
      if (g_visited[nz] == g_vid) continue;

      after_score += update_component(nz);
    }

    return after_score - before_score;
  }

  int clear_component(int z) {
    int key = g_component_key[z];
    int rz = (key >> 10) & Z_MASK;
    int size = g_component_key[rz] & Z_MASK;
    if (size == 0) return 0;

    g_component_key[rz] &= CLEAR_MASK;
    return calc_size_score(size);
  }

  int update_component(int z) {
    int key = build_key(z);
    int size = find_components(z, key);
    g_component_key[z] = key + size;

    return calc_size_score(size);
  }

  int find_components(int z, int key) {
    int size = 1;
    g_visited[z] = g_vid;
    g_component_key[z] = key;

    for (int dir = 0; dir < 4; ++dir) {
      int nz = z + DZ[dir];
      if (g_grid[nz] != g_grid[z]) continue;
      if (g_visited[nz] == g_vid) continue;

      size += find_components(nz, key);
    }

    return size;
  }

  vector <Command> run() {
    high_resolution_clock::time_point begin = high_resolution_clock::now();
    load_data();
    setup();

    search_best_grid(SA_TIME_LIMIT);

    int min_size = 9999;
    vector <Command> best_commands;
    double cur_time = get_time(begin);
    int build_cnt = 0;
    do {
      build_mst();

      vector <Command> commands;

      for (int i = 0; i < 3; ++i) {
        commands = build_commands(min_size);

        if (min_size > commands.size()) {
          min_size = commands.size();
          best_commands = commands;
          fprintf(stderr, "cmd_size: %d\n", (int) commands.size());
        }

        ++build_cnt;
      }

      cur_time = get_time(begin);
    } while (cur_time < MST_TIME_LIMIT);

    fprintf(stderr, "time: %f, build_cnt: %d\n", cur_time, build_cnt);
    return best_commands;
  }
};

int main() {
  HappyGrid hg;
  vector <Command> commands = hg.run();

  cout << commands.size() << endl;
  for (Command &cmd : commands) {
    cout << cmd.to_s() << endl;
  }

  cout.flush();
  return 0;
}