MM150 last submission

QueenAttack.cpp

#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <cfloat>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const int INF = INT_MAX;
const ll CYCLE_PER_SEC = 2700000000;
double TIME_LIMIT = 0.1;

const int OUT_OF_RANGE = -2;
const int WALL = -1;
const int EMPTY = 0;

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

const int MAX_C = 6;
const int MAX_N = 30;
const int GRID_SIZE = MAX_N + 2;
const int DZ[8] = {
  -GRID_SIZE - 1, -GRID_SIZE, -GRID_SIZE + 1,
  -1, 1,
  GRID_SIZE - 1, GRID_SIZE, GRID_SIZE + 1
};

int g_grid[GRID_SIZE * GRID_SIZE];
int g_grid_origin[GRID_SIZE * GRID_SIZE];
int g_queen_counter_all[GRID_SIZE * GRID_SIZE][MAX_C + 1];
double g_path_cost[GRID_SIZE * GRID_SIZE][GRID_SIZE * GRID_SIZE];
double g_raw_path_cost[GRID_SIZE * GRID_SIZE][GRID_SIZE * GRID_SIZE];
double g_sqrt_table[GRID_SIZE];
ll g_visited[GRID_SIZE * GRID_SIZE];
ll g_vid;
vector<int> g_line_positions[GRID_SIZE * GRID_SIZE][8];

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

int N, C, Q;

struct Command {
  int from_z;
  int to_z;

  Command(int from_z = -1, int to_z = -1) {
    this->from_z = from_z;
    this->to_z = to_z;
  }

  string to_str() {
    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 Edge {
  int to;
  int cap;
  int rev;
  double cost;

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

struct Node {
  int z;
  double cost;
  double penalty;
  double raw_cost;
  int bz;

  Node(int z = -1, double cost = 0, double penalty = 0, int bz = -1, double raw_cost = 0.0) {
    this->z = z;
    this->cost = cost;
    this->penalty = penalty;
    this->raw_cost = raw_cost;
    this->bz = bz;
  }

  bool operator>(const Node &n) const {
    return cost + penalty > n.cost + n.penalty;
  }
};

class MinCostFlow {
public:
  int V;
  vector<int> h;
  vector<double> dist;
  vector<int> prevv;
  vector<int> preve;
  vector <vector<Edge>> G;

  MinCostFlow(int V) {
    this->V = V;
    h.resize(V);
    dist.resize(V);
    prevv.resize(V);
    preve.resize(V);
    G.resize(V);
  }

  void add_edge(int from, int to, int cap, int cost) {
    G[from].push_back(Edge(to, cap, G[to].size(), cost));
    G[to].push_back(Edge(from, 0, G[from].size() - 1, -cost));
  }

  double min_cost_flow(int s, int t, int flow_limit) {
    int f = 0;
    ll total_cost = 0;
    fill(h.begin(), h.end(), 0);

    while (f < flow_limit) {
      // fprintf(stderr, "f: %d, limit: %d\n", f, flow_limit);
      priority_queue <P, vector<P>, greater<P>> pque;
      fill(dist.begin(), dist.end(), INF);
      dist[s] = 0;
      pque.push(P(0, s));

      while (!pque.empty()) {
        P p = pque.top();
        pque.pop();
        int v = p.second;
        if (dist[v] < p.first) continue;

        for (int i = 0; i < (int) G[v].size(); ++i) {
          Edge *edge = &G[v][i];
          if (edge->cap <= 0) continue;

          ll cost = edge->cost + h[v] - h[edge->to];
          if (dist[edge->to] - dist[v] > cost) {
            dist[edge->to] = dist[v] + cost;
            prevv[edge->to] = v;
            preve[edge->to] = i;
            pque.push(P(dist[edge->to], edge->to));
          }
        }
      }

      if (dist[t] == INF) {
        return -1;
      }

      for (int v = 0; v < V; ++v) {
        h[v] += dist[v];
      }

      int c = flow_limit - f;
      for (int v = t; v != s; v = prevv[v]) {
        c = min(c, G[prevv[v]][preve[v]].cap);
      }

      f += c;
      total_cost += c * h[t];

      // fprintf(stderr, "h[s]: %d, h[t]: %d, cost: %d, prev_cost: %d\n", h[s], h[t], cost, prev_cost);

      for (int v = t; v != s; v = prevv[v]) {
        Edge *edge = &G[prevv[v]][preve[v]];
        edge->cap -= c;
        G[v][edge->rev].cap += c;
      }
    }

    return total_cost;
  }
};

class QueenAttack {
public:
  void load_data() {
    memset(g_visited, -1, sizeof(g_visited));
    memset(g_grid, WALL, sizeof(g_grid));
    memset(g_sqrt_table, 0, sizeof(g_sqrt_table));
    g_vid = 0;

    cin >> N;
    cin >> C;
    fprintf(stderr, "N = %d\n", N);
    fprintf(stderr, "C = %d\n", C);
    Q = 0;

    for (int y = 0; y < GRID_SIZE; ++y) {
      for (int x = 0; x < GRID_SIZE; ++x) {
        int z = calc_z(y, x);
        if (y == 0 || y == N + 1 || x == 0 || x == N + 1) {
          g_grid[z] = OUT_OF_RANGE;
        }
      }
    }

    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        int c;
        cin >> c;
        int key = z * 8 + c;
        if (c == EMPTY) {
          g_grid[z] = EMPTY;
        } else if (c == WALL) {
          g_grid[z] = WALL;
        } else {
          g_grid[z] = key;
          ++Q;
        }
      }
    }
    fprintf(stderr, "Q = %d\n", Q);

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

    for (int d = 0; d < GRID_SIZE; ++d) {
      g_sqrt_table[d] = sqrt(d);
    }
  }

  void setup_line_positions() {
    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);

        for (int dir = 0; dir < 8; ++dir) {
          for (int l = 1; l <= N; ++l) {
            int nz = z + DZ[dir] * l;
            if (g_grid[nz] == OUT_OF_RANGE) break;
            if (g_grid[nz] == WALL) break;
            g_line_positions[z][dir].push_back(nz);
          }
        }
      }
    }
  }

  void setup_path_cost() {
    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int cz = calc_z(y, x);
        priority_queue <Node, vector<Node>, greater<Node>> pque;
        vector<double> min_cost(GRID_SIZE * GRID_SIZE, DBL_MAX);
        pque.push(Node(cz, 0));
        ++g_vid;

        while (not pque.empty()) {
          Node node = pque.top();
          int cy = node.z / GRID_SIZE;
          int cx = node.z % GRID_SIZE;
          pque.pop();

          if (g_visited[node.z] == g_vid) continue;
          g_visited[node.z] = g_vid;
          g_path_cost[cz][node.z] = node.cost + node.penalty;
          g_raw_path_cost[cz][node.z] = node.raw_cost;
          // fprintf(stderr, "(%d, %d) -> (%d, %d) cost = %lf\n", y, x, cy, cx, node.cost + node.penalty);

          for (int dir = 0; dir < 8; ++dir) {
            double penalty = 0.0;
            for (int l = 1; l <= N; ++l) {
              int nz = node.z + DZ[dir] * l;
              int ny = nz / GRID_SIZE;
              int nx = nz % GRID_SIZE;
              if (g_grid[nz] == OUT_OF_RANGE) break;
              if (g_grid[nz] == WALL) break;
              if (g_visited[nz] == g_vid) continue;

              int dy = ny - cy;
              int dx = nx - cx;
              double n_cost = node.cost + sqrt(dy * dy + dx * dx);
              if (g_grid[nz] != EMPTY) {
                penalty += 4.0;
              }
              double raw_cost = node.raw_cost + sqrt(max(abs(dy), abs(dx)));
              double n_penalty = node.penalty + penalty;
              if (min_cost[nz] > n_cost + n_penalty) {
                min_cost[nz] = n_cost + n_penalty;
                pque.push(Node(nz, n_cost, n_penalty, -1, raw_cost));
              }
            }
          }
        }
      }
    }
  }

  vector <Command> rebuild_commands(ll start_cycle, vector <Command> &commands) {
    memcpy(g_grid, g_grid_origin, sizeof(g_grid_origin));
    for (Command &cmd : commands) {
      swap(g_grid[cmd.from_z], g_grid[cmd.to_z]);
    }
    int temp_grid[GRID_SIZE * GRID_SIZE];
    memcpy(temp_grid, g_grid, sizeof(g_grid));
    vector <Command> best_commands = commands;
    double best_score = calc_score_raw(best_commands);
    int rebuid_cnt = 0;

    while (get_time(start_cycle) < 9.5) {
      memcpy(g_grid, temp_grid, sizeof(g_grid));
      vector <Command> new_commands = build_commands(true);
      double score = calc_score_raw(new_commands);

      if (best_score > score) {
        best_score = score;
        best_commands = new_commands;
        fprintf(stderr, "updated_score: %lf\n", best_score);
      }

      ++rebuid_cnt;
    }

    fprintf(stderr, "rebuild_cnt: %d\n", rebuid_cnt);
    return best_commands;
  }

  void run() {
    ll start_cycle = get_cycle();
    load_data();
    // show_grid();
    setup_path_cost();
    setup_line_positions();

    fprintf(stderr, "start_at: %lf\n", get_time(start_cycle));
    vector <Command> best_commands;
    double best_score = DBL_MAX;
    double time_limit = 0.1;

    while (get_time(start_cycle) < 8.0) {
      vector <Command> commands = search_commands(time_limit);
      double score = calc_score_raw(commands);

      if (best_score > score) {
        best_score = score;
        best_commands = commands;
      }
    }

    best_commands = rebuild_commands(start_cycle, best_commands);

    double finished_at = get_time(start_cycle);
    if (finished_at > 10.0) {
      fprintf(stderr, "TimeLimitExceeded\n");
    }

    fprintf(stderr, "finished_at: %lf, best_score: %lf\n", finished_at, calc_score_raw(best_commands));

    cout << best_commands.size() << endl;
    for (int i = 0; i < best_commands.size(); ++i) {
      cout << best_commands[i].to_str() << endl;
    }
  }

  vector <Command> search_commands(double time_limit) {
    memcpy(g_grid, g_grid_origin, sizeof(g_grid_origin));
    sa(time_limit);

    int temp_grid[GRID_SIZE * GRID_SIZE];
    memcpy(temp_grid, g_grid, sizeof(g_grid));
    double best_score = DBL_MAX;
    vector <Command> best_commands;

    for (int i = 0; i < 3; ++i) {
      memcpy(g_grid, temp_grid, sizeof(g_grid));
      for (int color = 1; color <= C; ++color) {
        mapping_target_z(color, i);
      }
      vector <Command> commands = build_commands();
      double score = calc_score_raw(commands);

      if (best_score > score) {
        best_score = score;
        best_commands = commands;
      }
    }

    return best_commands;
  }

  double calc_score_raw(vector <Command> &commands) {
    memcpy(g_grid, g_grid_origin, sizeof(g_grid_origin));
    for (int i = 0; i < commands.size(); ++i) {
      swap(g_grid[commands[i].from_z], g_grid[commands[i].to_z]);
    }

    double commands_cost = calc_commands_cost(commands);
    double error_score = countErrors() * N;

    return error_score + commands_cost;
  }

  double calc_commands_cost(vector <Command> &commands) {
    double cost = 0.0;

    for (Command &cmd : commands) {
      int from_y = cmd.from_z / GRID_SIZE;
      int from_x = cmd.from_z % GRID_SIZE;
      int to_y = cmd.to_z / GRID_SIZE;
      int to_x = cmd.to_z % GRID_SIZE;
      int dy = abs(from_y - to_y);
      int dx = abs(from_x - to_x);
      cost += sqrt(max(dy, dx));
    }

    return cost;
  }

  void mapping_target_z(int color, int type) {
    vector<int> base_positions;
    vector<int> target_positions;
    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        if (g_grid[z] == EMPTY) continue;
        if (g_grid[z] == WALL) continue;
        int key = g_grid[z];
        int bz = key >> 3;
        int c = key & 7;
        if (c == color) {
          base_positions.push_back(bz);
          target_positions.push_back(z);
        }
      }
    }

    int V = 2 * target_positions.size() + 2;
    int S = V - 2;
    int T = V - 1;
    MinCostFlow mcf(V);

    for (int i = 0; i < base_positions.size(); ++i) {
      int bz = base_positions[i];

      mcf.add_edge(S, i, 1, 0);

      for (int j = 0; j < target_positions.size(); ++j) {
        int tz = target_positions[j];
        double cost = g_path_cost[bz][tz];
        if (type == 1) {
          int by = bz / GRID_SIZE;
          int bx = bz % GRID_SIZE;
          int ty = tz / GRID_SIZE;
          int tx = tz % GRID_SIZE;
          cost = sqrt((by - ty) * (by - ty) + (bx - tx) * (bx - tx));
        } else if (type == 2) {
          cost = g_raw_path_cost[bz][tz];
        }

        mcf.add_edge(i, j + base_positions.size(), 1, cost);
      }
    }

    for (int j = 0; j < target_positions.size(); ++j) {
      mcf.add_edge(j + base_positions.size(), T, 1, 0);
    }

    mcf.min_cost_flow(S, T, base_positions.size());
    for (int i = 0; i < base_positions.size(); ++i) {
      int bz = base_positions[i];

      for (Edge &e : mcf.G[i]) {
        if (e.to == S) continue;
        if (e.cap > 0) continue;
        int tz = target_positions[e.to - base_positions.size()];

        int n_key = bz * 8 + color;
        g_grid[tz] = n_key;
        // fprintf(stderr, "(%d, %d) -> (%d, %d)\n", bz / GRID_SIZE, bz % GRID_SIZE, tz / GRID_SIZE, tz % GRID_SIZE);
      }
    }
  }

  vector <Command> build_commands(double with_random_cost = false) {
    vector <Command> commands;
    map<int, int> to_z_list;

    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        if (g_grid[z] == EMPTY) continue;
        if (g_grid[z] == WALL) continue;
        int key = g_grid[z];
        int bz = key >> 3;

        to_z_list[bz] = z;
      }
    }

    memcpy(g_grid, g_grid_origin, sizeof(g_grid_origin));
    bool updated = true;

    while (updated) {
      updated = false;
      double min_cost = DBL_MAX;
      int cur_z = -1;
      int from_z = -1;

      for (int y = 1; y <= N; ++y) {
        for (int x = 1; x <= N; ++x) {
          int z = calc_z(y, x);
          if (g_grid[z] == EMPTY) continue;
          if (g_grid[z] == WALL) continue;
          int key = g_grid[z];
          int bz = key >> 3;
          int tz = to_z_list[bz];
          if (tz == z) continue;
          if (g_grid[tz] != EMPTY) continue;

          double cost = calc_path_cost(z, tz, min_cost);
          if (with_random_cost) {
            cost += 0.1 * (xor128() % 1000);
          }

          if (min_cost > cost) {
            min_cost = cost;
            cur_z = z;
            from_z = bz;
          }
        }
      }

      if (from_z == -1) {
        break;
      }

      updated = true;
      int to_z = to_z_list[from_z];
      vector <Command> path = find_path(cur_z, to_z);
      assert(path.size() > 0);
      assert(g_grid[to_z] == EMPTY);
      swap(g_grid[cur_z], g_grid[to_z]);
      commands.insert(commands.end(), path.begin(), path.end());
    }

    return commands;
  }

  vector <Command> find_path(int from_z, int to_z) {
    priority_queue <Node, vector<Node>, greater<Node>> pque;
    vector<double> min_cost(GRID_SIZE * GRID_SIZE, DBL_MAX);
    pque.push(Node(from_z, 0));
    ++g_vid;
    int history[GRID_SIZE * GRID_SIZE];
    memset(history, -1, sizeof(history));

    while (not pque.empty()) {
      Node node = pque.top();
      int cy = node.z / GRID_SIZE;
      int cx = node.z % GRID_SIZE;
      pque.pop();

      if (g_visited[node.z] == g_vid) continue;
      g_visited[node.z] = g_vid;
      history[node.z] = node.bz;

      if (node.z == to_z) {
        vector <Command> commands;
        int z = to_z;
        while (z != from_z) {
          int bz = history[z];
          commands.push_back(Command(bz, z));
          z = bz;
        }
        reverse(commands.begin(), commands.end());
        return commands;
      }

      for (int dir = 0; dir < 8; ++dir) {
        double penalty = 0.0;
        for (int nz : g_line_positions[node.z][dir]) {
          if (g_visited[nz] == g_vid) continue;
          int ny = nz / GRID_SIZE;
          int nx = nz % GRID_SIZE;
          if (g_grid[nz] != EMPTY) break;
          int dy = abs(ny - cy);
          int dx = abs(nx - cx);

          double n_cost = node.cost + g_sqrt_table[max(dy, dx)];
          double n_penalty = node.penalty + penalty;
          double value = n_cost + n_penalty;

          if (min_cost[nz] > value) {
            min_cost[nz] = value;
            pque.push(Node(nz, n_cost, n_penalty, node.z));
          }
        }
      }
    }

    return vector<Command>();
  }

  double calc_path_cost(int from_z, int to_z, double cur_min_cost) {
    priority_queue <Node, vector<Node>, greater<Node>> pque;
    vector<double> min_cost(GRID_SIZE * GRID_SIZE, cur_min_cost);
    pque.push(Node(from_z, 0));
    ++g_vid;

    while (not pque.empty()) {
      Node node = pque.top();
      int cy = node.z / GRID_SIZE;
      int cx = node.z % GRID_SIZE;
      pque.pop();

      if (g_visited[node.z] == g_vid) continue;
      g_visited[node.z] = g_vid;

      if (node.z == to_z) {
        return node.cost + node.penalty;
      }

      for (int dir = 0; dir < 8; ++dir) {
        double penalty = 0.0;
        for (int nz : g_line_positions[node.z][dir]) {
          if (g_visited[nz] == g_vid) continue;
          int ny = nz / GRID_SIZE;
          int nx = nz % GRID_SIZE;
          if (g_grid[nz] != EMPTY) break;
          int dy = abs(ny - cy);
          int dx = abs(nx - cx);

          double n_cost = node.cost + g_sqrt_table[max(dy, dx)];
          double n_penalty = node.penalty + penalty;
          double value = n_cost + n_penalty;

          if (min_cost[nz] > value) {
            min_cost[nz] = value;
            pque.push(Node(nz, n_cost, n_penalty));
          }
        }
      }
    }

    return DBL_MAX;
  }

  void sa(double time_limit = TIME_LIMIT) {
    ll start_cycle = get_cycle();

    double cur_score = calc_score_full();
    double best_score = cur_score;
    int best_grid[GRID_SIZE * GRID_SIZE];
    memcpy(best_grid, g_grid, sizeof(g_grid));

    double cur_time = get_time(start_cycle);
    double total_diff = 0.0;
    double t = 0.1;
    ll R = 100000000;
    ll try_count = 0;
    int queen_positions[Q];
    int empty_positions[GRID_SIZE * GRID_SIZE - Q];
    int q_idx = 0;
    int e_idx = 0;
    int E = 0;
    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        if (g_grid[z] == EMPTY) {
          empty_positions[e_idx] = z;
          ++e_idx;
          ++E;
          continue;
        }
        if (g_grid[z] == WALL) continue;

        queen_positions[q_idx] = z;
        ++q_idx;
      }
    }
    int cur_errors = countErrors();
    int L = 200000;
    int random_table[L];
    int random_table_q[L];
    for (int i = 0; i < L; ++i) {
      random_table[i] = xor128() % E;
      random_table_q[i] = xor128() % Q;
    }

    while (cur_time < time_limit) {
      cur_time = get_time(start_cycle);
      double remain_time = (time_limit - cur_time) / time_limit;
      assert(g_grid[calc_z(0, 1)] == OUT_OF_RANGE);

      int z = -1;
      int best_idx = -1;
      int max_cnt = -1;
      ++g_vid;
      for (int i = 0; i < N; ++i) {
        int idx = random_table_q[(try_count * N + i) % L];
        int cz = queen_positions[idx];

        int cnt = g_queen_counter_all[cz][g_grid[cz] & 7];
        if (max_cnt < cnt) {
          max_cnt = cnt;
          best_idx = idx;
          z = cz;
        }
      }
      if (best_idx == -1) continue;

      int key = g_grid[z];
      int bz = (key >> 3);
      int color = key & 7;
      double beore_path_cost = g_path_cost[bz][z];

      int nz = -1;
      int limit = 4 * N;
      int min_cnt = INF;
      int best_e_idx = -1;
      ++g_vid;

      remove_queen_all(z, key);
      for (int i = 0; i < limit && min_cnt > 0; ++i) {
        int idx = random_table[(try_count * (N * 4) + i) % L];
        int pz = empty_positions[idx];
        int cnt = g_queen_counter_all[pz][color];

        if (min_cnt > cnt) {
          min_cnt = cnt;
          nz = pz;
          best_e_idx = idx;
        }
      }

      if (nz == -1) {
        add_queen_all(z, key);
        continue;
      }

      assert(g_grid[nz] == EMPTY);
      int diff_errors = min_cnt - max_cnt;
      double after_path_cost = g_path_cost[bz][nz];
      // assert(cur_errors + diff_errors == countErrors());
      double score = cur_score;
      score += (after_path_cost - beore_path_cost);
      score += diff_errors * N;
      // assert(abs(score - calc_score_full()) < 1e-6);

      double diff_score = cur_score - score;
      total_diff += fabs(diff_score);

      if (diff_score > 0 || (xor128() % R < R * exp(diff_score / (t * sqrt(remain_time))))) {
        add_queen_all(nz, key);
        cur_score = score;
        empty_positions[best_e_idx] = z;
        queen_positions[best_idx] = nz;
        cur_errors += diff_errors;

        if (best_score > score) {
          best_score = score;
          memcpy(best_grid, g_grid, sizeof(g_grid));
          if (cur_errors == 0) break;
        }
      } else {
        add_queen_all(z, key);
      }

      ++try_count;
      double average_diff = total_diff / try_count;
      t = 0.15 * remain_time * average_diff;
    }

    assert(g_grid[calc_z(0, 1)] == OUT_OF_RANGE);
    memcpy(g_grid, best_grid, sizeof(best_grid));
    fprintf(stderr, "try_count: %lld, best_score: %lf, errors: %d\n", try_count, best_score, countErrors());
  }

  void add_queen_all(int z, int key) {
    int c = key & 7;
    g_grid[z] = key;

    for (int dir = 0; dir < 8; ++dir) {
      for (int l = 1; l <= N; ++l) {
        int nz = z + DZ[dir] * l;
        if (g_grid[nz] == OUT_OF_RANGE) break;

        ++g_queen_counter_all[nz][c];
      }
    }
  }

  void remove_queen_all(int z, int key) {
    int c = key & 7;
    g_grid[z] = EMPTY;

    for (int dir = 0; dir < 8; ++dir) {
      for (int l = 1; l <= N; ++l) {
        int nz = z + DZ[dir] * l;
        if (g_grid[nz] == OUT_OF_RANGE) break;

        --g_queen_counter_all[nz][c];
      }
    }
  }

  double calc_score_full() {
    memset(g_queen_counter_all, 0, sizeof(g_queen_counter_all));

    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        if (g_grid[z] == EMPTY) continue;
        if (g_grid[z] == WALL) continue;
        int key = g_grid[z];
        int bz = key >> 3;
        int c = key & 7;

        // fprintf(stderr, "(%d, %d, key: %d)\n", bz, z, key);
        assert(bz >= 0 && bz < GRID_SIZE * GRID_SIZE);

        for (int dir = 0; dir < 8; ++dir) {
          for (int l = 1; l <= N; ++l) {
            int nz = z + DZ[dir] * l;
            if (g_grid[nz] == OUT_OF_RANGE) break;

            g_queen_counter_all[nz][c]++;
          }
        }
      }
    }

    return countErrors() * N;
  }

  int countErrors() {
    int num_errors = 0;

    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        int z = calc_z(y, x);
        if (g_grid[z] == EMPTY) continue;
        if (g_grid[z] == WALL) continue;
        int key = g_grid[z];
        int c = key & 7;
        assert(g_grid[z] != OUT_OF_RANGE);

        for (int dir = 0; dir < 8; ++dir) {
          for (int l = 1; l <= N; ++l) {
            int nz = z + DZ[dir] * l;
            if (g_grid[nz] == WALL) continue;
            if (g_grid[nz] == EMPTY) continue;
            if (g_grid[nz] == OUT_OF_RANGE) break;
            int n_key = g_grid[nz];
            int nc = n_key & 7;
            if (c != nc) continue;

            assert(1 <= nc && nc <= MAX_C);
            ++num_errors;
          }
        }
      }
    }

    return num_errors / 2;
  }

  void show_grid() {
    for (int y = 0; y <= N + 1; ++y) {
      for (int x = 0; x <= N + 1; ++x) {
        int z = calc_z(y, x);
        int key = g_grid[z];
        int c = key & 7;

        if (g_grid[z] == OUT_OF_RANGE) {
          fprintf(stderr, "#");
        } else if (g_grid[z] == WALL) {
          fprintf(stderr, "X");
        } else if (g_grid[z] == EMPTY) {
          fprintf(stderr, " ");
        } else {
          fprintf(stderr, "%d", c);
        }
      }
      fprintf(stderr, "\n");
    }
  }
};

int main() {
  QueenAttack queen_attack;
  queen_attack.run();

  cout << 0 << endl;
  return 0;
}