Submission #50876874

---

Source Code Expand

#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define LOG(x) cerr << #x << " = " << x << endl
#define dump(x) cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl
using namespace std;

// template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
// template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

// using ll = long long;
// using ld = long double;
// using P = pair<int,int>;

int T, N;
std::vector<std::vector<int> > V;
std::vector<std::vector<int> > H;
std::vector<std::vector<int> > A;

namespace ats5515 {
const int64_t CYCLES_PER_SEC = 2900000000;
const double TIMELIMIT = 2.95;
struct Timer {
	int64_t start;
	Timer() { reset(); }
	void reset() { start = getCycle(); }
	void plus(double a) { start -= (a * CYCLES_PER_SEC); }
	inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; }
	inline int64_t getCycle() {
		uint32_t low, high;
		__asm__ volatile("rdtsc" : "=a"(low), "=d"(high));
		return ((int64_t)low) | ((int64_t)high << 32);
	}
};
class XorShift {
   public:
	unsigned int x, y, z, w;
	double nL[65536];

	XorShift() {
		init();
	}

	void init() {
		x = 314159265;
		y = 358979323;
		z = 846264338;
		w = 327950288;
		double n = 1 / (double)(2 * 65536);
		for (int i = 0; i < 65536; i++) {
			nL[i] = log(((double)i / 65536) + n);
		}
	}

	inline unsigned int next() {
		unsigned int t = x ^ x << 11;
		x = y;
		y = z;
		z = w;
		return w = w ^ w >> 19 ^ t ^ t >> 8;
	}

	inline double nextLog() {
		return nL[next() & 0xFFFF];
	}

	inline int nextInt(int m) {
		return (int)(next() % m);
	}

	int nextInt(int min, int max) {
		return min + nextInt(max - min + 1);
	}

	inline double nextDouble() {
		return (double)next() / ((long long)1 << 32);
	}
};
XorShift rnd;
const int DX[4] = {1, 0, -1, 0};
const int DY[4] = {0, 1, 0, -1};
const int REV[4] = {2, 3, 0, 1};
const char DIRCHAR[4] = {'D', 'R', 'U', 'L'};
std::vector<std::vector<int> > distance_matrix;
std::vector<std::vector<int> > adjacent_cells;
std::vector<std::vector<int> > near_cells;
void precalc_distance_matrix() {
	distance_matrix.resize(N * N);
	adjacent_cells.resize(N * N);
	for (int i = 0; i < N * N; i++) {
		distance_matrix[i].resize(N * N, (int)1e9);
	}
	for (int i = 0; i < N * N; i++) {
		distance_matrix[i][i] = 0;
		int x = i / N;
		int y = i % N;

		if (x < N - 1) {
			if (H[x][y] == 0) {
				int j = (x + 1) * N + y;
				adjacent_cells[i].push_back(j);
				adjacent_cells[j].push_back(i);
			}
		}
		if (y < N - 1) {
			if (V[x][y] == 0) {
				int j = x * N + y + 1;
				adjacent_cells[i].push_back(j);
				adjacent_cells[j].push_back(i);
			}
		}
	}

	for (int i = 0; i < N * N; i++) {
		queue<int> qu;
		qu.push(i);
		while (!qu.empty()) {
			int j = qu.front();
			qu.pop();
			for (int &k : adjacent_cells[j]) {
				if (distance_matrix[i][k] > distance_matrix[i][j] + 1) {
					distance_matrix[i][k] = distance_matrix[i][j] + 1;
					qu.push(k);
				}
			}
		}
	}

	near_cells.resize(N * N);
	for (int i = 0; i < N * N; i++) {
		for (int j = 0; j < N * N; j++) {
			if (distance_matrix[i][j] <= 10) {
				near_cells[i].push_back(j);
			}
		}
	}
}
int N_boundary = 20;
Timer timer;
pair<vector<pair<int, int> >, int> solve_once(double timelimit, int noise) {
	int N2 = N * N;
	int cur_pos1 = -1;
	int cur_pos2 = -1;
	int turns_left = 4 * N2;

	// turns_left = 1;
	vector<pair<int, int> > res;
	std::vector<int> cur_A(N2, 0);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cur_A[i * N + j] = A[i][j];
		}
	}
	long int total_score_diff = 0;
	int cntmax = 100000;
	vector<pair<int, int> > N2_pairs;
	if (N <= N_boundary) {
		for (int i = 0; i < N * N; i++) {
			for (int j = 0; j < i; j++) {
				N2_pairs.emplace_back(i, j);
			}
		}
		cntmax = N2_pairs.size();
	} else {
		if (N >= 30) {
			cntmax = 100000;
		}
		if (N >= 40) {
			cntmax = 100000;
		}
		if (N >= 50) {
			cntmax = 40000;
		}
		if (N >= 100) {
			cntmax = 10000;
		}
	}

	double last_iter_time = -1;
	int niters = 0;
	while (turns_left > 0) {
		double cur_time = timer.get();
		if (cur_time > timelimit) break;
		double best_eval_diff = 1e-5;
		int best_score_diff = -1;
		int best_pos1 = -1;
		int best_pos2 = -1;
		int best_turns_left = 0;
		int cnt = 0;
		if (N > N_boundary) {
			if (last_iter_time > 0) {
				double move_per_turn = (4 * N2 - turns_left) / (double)(res.size());
				double expected_iters_left = turns_left / move_per_turn;
				double time_left = timelimit - cur_time;
				double next_iter_timelimit = time_left / max(1.0, expected_iters_left);
				double new_cntmax = (cntmax / last_iter_time) * next_iter_timelimit;
				double progress1to0 = 4.0 * N2 / turns_left;
				cntmax = 0.1 * cntmax + 0.9 * new_cntmax;
				cntmax = min(cntmax, 200000) * (1 + progress1to0 * 0.4);
				// if (niters % 100 == 0) {
				// 	cerr << "cntmax = " << cntmax << endl;
				// }
			}
		}
		niters++;

		// for (int i = 0; i < N2; i++) {
		// 	if (timer.get() > 1.8) break;
		// 	for (int j = 0; j < i; j++) {
		{
			while (cnt < cntmax) {
				if ((cnt & ((1 << 8) - 1)) == 0) {
					if (timer.get() > timelimit) break;
				}
				// if (best_pos1 == -1 && cnt >= 100) break;
				int i;
				int j;
				if (N <= N_boundary) {
					i = N2_pairs[cnt].first;
					j = N2_pairs[cnt].second;
				} else {
					if (cur_pos1 == -1) {
						// if(true){
						i = rnd.nextInt(N2);
						j = rnd.nextInt(N2 - 1);
						if (j >= i) j++;
					} else {
						while (true) {
							if (rnd.nextInt(2) == 0) {
								i = rnd.nextInt(N2);
							} else {
								i = near_cells[cur_pos1][rnd.nextInt(near_cells[cur_pos1].size())];
							}
							if (rnd.nextInt(2) == 0) {
								j = rnd.nextInt(N2);
							} else {
								j = near_cells[cur_pos2][rnd.nextInt(near_cells[cur_pos2].size())];
							}
							if (i != j) break;
						}
					}
				}
				cnt++;
				// cerr << i << " " << j << " " << turns_left << endl;
				int turns_take = 1;
				int new_pos1, new_pos2;
				if (cur_pos1 != -1) {
					int turns_take1 = max(distance_matrix[cur_pos1][i], distance_matrix[cur_pos2][j]);
					int turns_take2 = max(distance_matrix[cur_pos1][j], distance_matrix[cur_pos2][i]);
					if (turns_take1 <= turns_take2) {
						new_pos1 = i;
						new_pos2 = j;
						turns_take = turns_take1;
					} else {
						new_pos1 = j;
						new_pos2 = i;
						turns_take = turns_take2;
					}
				} else {
					new_pos1 = i;
					new_pos2 = j;
				}
				if (turns_left < turns_take) continue;
				// calc_score_diff
				int score_diff = 0;
				for (int k : adjacent_cells[new_pos1]) {
					if (k == new_pos2) continue;
					score_diff -= (cur_A[new_pos1] - cur_A[k]) * (cur_A[new_pos1] - cur_A[k]);
					score_diff += (cur_A[new_pos2] - cur_A[k]) * (cur_A[new_pos2] - cur_A[k]);
				}
				for (int k : adjacent_cells[new_pos2]) {
					if (k == new_pos1) continue;
					score_diff -= (cur_A[new_pos2] - cur_A[k]) * (cur_A[new_pos2] - cur_A[k]);
					score_diff += (cur_A[new_pos1] - cur_A[k]) * (cur_A[new_pos1] - cur_A[k]);
				}
				// swap(cur_A[new_pos1], cur_A[new_pos2]);
				// for (int k : adjacent_cells[new_pos1]) {
				// 	score_diff += (cur_A[new_pos1] - cur_A[k]) * (cur_A[new_pos1] - cur_A[k]);
				// }
				// for (int k : adjacent_cells[new_pos2]) {
				// 	if (k == new_pos1) continue;
				// 	score_diff += (cur_A[new_pos2] - cur_A[k]) * (cur_A[new_pos2] - cur_A[k]);
				// }
				// swap(cur_A[new_pos1], cur_A[new_pos2]);

				double eval_diff = score_diff / (turns_take + 0.0);
				if (noise > 0) {
					eval_diff += rnd.nextDouble() * 100;
				}
				if (best_eval_diff > eval_diff) {
					best_eval_diff = eval_diff;
					best_score_diff = score_diff;
					best_pos1 = new_pos1;
					best_pos2 = new_pos2;
					best_turns_left = turns_left - turns_take;
				}
			}
		}

		if (best_eval_diff > 0) {
			break;
		}
		cur_pos1 = best_pos1;
		cur_pos2 = best_pos2;
		turns_left = best_turns_left;
		total_score_diff += best_score_diff;
		swap(cur_A[cur_pos1], cur_A[cur_pos2]);
		res.emplace_back(best_pos1, best_pos2);
		// cerr << best_score_diff << endl;
		double end_time = timer.get();
		last_iter_time = end_time - cur_time;
	}
	cerr << "total_score_diff = " << total_score_diff << endl;
	return pair<vector<pair<int, int> >, int>(res, total_score_diff);
}

void output(vector<pair<int, int> > &res) {
	cout << res[0].first / N << " " << res[0].first % N << " " << res[0].second / N << " " << res[0].second % N << '\n';
	int n_moves = 0;
	for (int i = 1; i < (int)res.size(); i++) {
		// cerr << "res " << i << "/" << res.size() <<" " <<  res[i].first / N << " " << res[i].first % N << " " << res[i].second / N << " " << res[i].second % N << '\n';
		int do_swap = 1;
		int pos[2];
		int pos_to[2];
		pos[0] = res[i - 1].first;
		pos[1] = res[i - 1].second;
		pos_to[0] = res[i].first;
		pos_to[1] = res[i].second;

		while (pos[0] != pos_to[0] || pos[1] != pos_to[1]) {
			char dir_char[2];

			for (int j = 0; j < 2; j++) {
				if (pos[j] == pos_to[j]) {
					dir_char[j] = '.';
					continue;
				}
				int x = pos[j] / N;
				int y = pos[j] % N;
				for (int dir = 0; dir < 4; dir++) {
					int xx = x + DX[dir];
					int yy = y + DY[dir];
					if (xx >= 0 && xx < N && yy >= 0 && yy < N) {
						int k = xx * N + yy;
						if (distance_matrix[pos[j]][k] == 1 &&
							(distance_matrix[pos[j]][pos_to[j]] > distance_matrix[k][pos_to[j]])) {
							dir_char[j] = DIRCHAR[dir];
							pos[j] = k;
							break;
						}
					}
				}
			}
			n_moves++;
			cout << do_swap << " " << dir_char[0] << " " << dir_char[1] << '\n';
			do_swap = 0;
		}
	}
	cout << "1 . ." << '\n';
	n_moves++;
	cerr << res.size() << endl;
	cerr << n_moves << endl;

	// for (int i = 0; i < N; i++) {
	// 	for (int j = 0; j < N; j++) {
	// 		cerr << cur_A[i * N + j] << " ";
	// 	}
	// 	cerr << endl;
	// }

	cerr << "time = " << timer.get() << endl;
}

void solve() {
	cerr << "N = " << N << endl;
	precalc_distance_matrix();
	cerr << timer.get() << endl;
	if (N <= N_boundary) {
	//if (false) {
		int best_score = 0;
		double timelimit = 1.95;
		vector<pair<int, int> > bestres;
		int noise = 0;
		while (true) {
			pair<vector<pair<int, int> >, int> res;
			res = solve_once(timelimit, noise);

			if (best_score > res.second) {
				best_score = res.second;
				bestres = res.first;
			}
			if (timer.get() > timelimit) {
				break;
			}
			noise++;
		}
		output(bestres);
	} else {
		double timelimit = 1.95;
		pair<vector<pair<int, int> >, int> res;
		res = solve_once(timelimit, 0);
		output(res.first);

	}
}
}  // namespace ats5515

namespace asi1024 {

class Timer {
public:
  int64_t start, stop;
  static const int64_t CYCLES_PER_SEC = 2900000000;
  inline int64_t get_cycle() const {
    uint32_t low, high;
    __asm__ volatile("rdtsc" : "=a"(low), "=d"(high));
    return int64_t(low) | (int64_t(high) << 32);
  }
  Timer(double time_limit) :
    start(get_cycle()), stop(start + time_limit * CYCLES_PER_SEC) {}
  Timer() : Timer(0) {}
  inline bool within(int64_t end) const { return get_cycle() < end; }
  inline bool within() const { return within(stop); }
};

Timer timer(1.95);

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

using ll = long long;
using ull = unsigned long long;
using Op2 = std::tuple<int, char, char>;

struct State {
  std::vector<short> board;
  std::vector<Op2> ops;
  int y1, x1, y2, x2;
  ll d2;

  int val(int y, int x) const {
    return board[y * N + x];
  }
  int dist_(int y1, int x1, int y2, int x2) const {
    int vd = val(y1, x1) - val(y2, x2);
    return vd * vd;
  }

  void reset_d2() {
    d2 = 0;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N - 1; ++j) {
        if (V[i][j] == 0) {
          d2 += dist_(i, j, i, j + 1);
        }
      }
    }
    for (int i = 0; i < N - 1; ++i) {
      for (int j = 0; j < N; ++j) {
        if (H[i][j] == 0) {
          d2 += dist_(i, j, i + 1, j);
        }
      }
    }
  }

  State() {}

  State(int y1, int x1, int y2, int x2): y1(y1), x1(x1), y2(y2), x2(x2), d2(0) {
    board.resize(N * N);
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        board[i * N + j] = A[i][j];
      }
    }
    reset_d2();
    ops.emplace_back(0, '.', '.');
  }

  void swap() {
    std::swap(board[y1 * N + x1], board[y2 * N + x2]);
    reset_d2();
  }

  ull hash() const {
    ull h = y1;
    h = h * 10007 + x1;
    h = h * 10007 + y2;
    h = h * 10007 + x2;
    h = h * 1000000007 + val(y1, x1);
    h = h * 1000000007 + val(y2, x2);
    return h;
  }
};

std::vector<Op2> beam_search(int sy1, int sx1, int sy2, int sx2) {
  int64_t start = timer.get_cycle();
  std::map<ull, State> states;
  ll init_d = -1;
  {
    State state(sy1, sx1, sy2, sx2);
    ull h = state.hash();
    init_d = state.d2;
    LOG(init_d);
    states[h] = state;
  }
  for (int i = 0; i < N * N * 4 - 1; ++i) {
    std::map<ull, State> next_states;
    auto push = [&](const State& state) {
      ull h = state.hash();
      if (next_states.count(h) == 0) {
        next_states[h] = state;
      } else if (next_states[h].d2 > state.d2) {
        next_states[h] = state;
      }
    };
    for (auto &pair : states) {
      State state = pair.second;
      int y1 = state.y1, x1 = state.x1, y2 = state.y2, x2 = state.x2;
      for (int dir1 = 0; dir1 < 5; ++dir1) {
        int ny1 = y1 + dy[dir1], nx1 = x1 + dx[dir1];
        if (ny1 < 0 || ny1 >= N || nx1 < 0 || nx1 >= N) continue;
        if (dir1 == 0 && V[y1][x1]) continue;
        if (dir1 == 1 && H[y1][x1]) continue;
        if (dir1 == 2 && V[y1][nx1]) continue;
        if (dir1 == 3 && H[ny1][x1]) continue;
        for (int dir2 = 0; dir2 < 5; ++dir2) {
          double elapsed = (timer.get_cycle() - start) / (double)Timer::CYCLES_PER_SEC;
          if (elapsed > 1.8 * (i + 1) / (N * N * 4) && next_states.size() >= 1) {
            break;
          }
          if (dir1 == 4 && dir2 == 4) continue;
          int ny2 = y2 + dy[dir2], nx2 = x2 + dx[dir2];
          if (ny2 < 0 || ny2 >= N || nx2 < 0 || nx2 >= N) continue;
          if (dir2 == 0 && V[y2][x2]) continue;
          if (dir2 == 1 && H[y2][x2]) continue;
          if (dir2 == 2 && V[y2][nx2]) continue;
          if (dir2 == 3 && H[ny2][x2]) continue;
          State next_state = state;
          std::get<1>(next_state.ops.back()) = "RDLU."[dir1];
          std::get<2>(next_state.ops.back()) = "RDLU."[dir2];
          next_state.ops.emplace_back(0, '.', '.');
          next_state.y1 = ny1;
          next_state.x1 = nx1;
          next_state.y2 = ny2;
          next_state.x2 = nx2;
          push(next_state);
          std::get<0>(next_state.ops.back()) = 1;
          next_state.swap();
          push(next_state);
        }
      }
    }

    std::vector<State> sorted_states;
    sorted_states.reserve(next_states.size());
    for (auto &pair : next_states) {
      sorted_states.emplace_back(pair.second);
    }
    std::sort(sorted_states.begin(), sorted_states.end(), [](const State &s1, const State &s2) {
      return s1.d2 < s2.d2;
    });
    if (sorted_states.size() > BEAM_WIDTH) sorted_states.resize(BEAM_WIDTH);
    states.clear();

    for (const State &state : sorted_states) {
      states[state.hash()] = state;
    }
    std::cerr << "beam_search: " << i << " " << states.size() << " " << sorted_states[0].d2 << std::endl;
  }
  
  std::optional<State> best_state = std::nullopt;
  for (auto &pair : states) {
    if (!best_state.has_value() || best_state->d2 > pair.second.d2) {
      best_state = pair.second;
    }
  }
  assert(best_state.has_value());
  LOG(best_state->d2);
  int score = std::max(1.0, std::round(1e6 * (std::log2(init_d) - std::log2(best_state->d2))));
  LOG(score);
  return best_state->ops;
}

void solve() {
  BEAM_WIDTH = 2;
  if (T == 0) BEAM_WIDTH = 200;
  else if (T == 1) BEAM_WIDTH = 200;
  else if (T == 2) BEAM_WIDTH = 25;
  else if (T == 3) BEAM_WIDTH = 15;
  else if (T == 4) BEAM_WIDTH = 10;
  else if (T == 5) BEAM_WIDTH = 6;
  else if (T == 6) BEAM_WIDTH = 6;
  else if (T == 7) BEAM_WIDTH = 15;
  else if (T == 8) BEAM_WIDTH = 6;
  else if (T == 9) BEAM_WIDTH = 1;
  else if (T == 10) BEAM_WIDTH = 1;
  else if (T == 11) BEAM_WIDTH = 1;
  else if (T == 12) BEAM_WIDTH = 1;
  else if (T == 13) BEAM_WIDTH = 1;
  else if (T == 14) BEAM_WIDTH = 1;
  else if (T == 15) BEAM_WIDTH = 1;
  else if (T == 16) BEAM_WIDTH = 1;
  else if (T == 17) BEAM_WIDTH = 1;
  else if (T == 18) BEAM_WIDTH = 1;
  else if (T == 19) BEAM_WIDTH = 1;
  BEAM_WIDTH *= 2;
  // if (T != 9) {
  //   std::cout << "0 0 0 0" << std::endl;
  //   return;
  // }

  int sy1 = 0, sx1 = 0, sy2 = N - 1, sx2 = N - 1;
  std::vector<std::vector<int>> visited(N, std::vector<int>(N, 0));
  auto ops = beam_search(sy1, sx1, sy2, sx2);

  std::cout << sy1 << " " << sx1 << " " << sy2 << " " << sx2 << std::endl;
  for (auto [t, c1, c2] : ops) {
    std::cout << t << " " << c1 << " " << c2 << std::endl;
  }
  double elapsed = (timer.get_cycle() - timer.start) / (double)Timer::CYCLES_PER_SEC;
  LOG(elapsed);
}

} // namespace asi1024



namespace hog {
  using vi = vector<int>;
  using ll = long long;
  using pii = pair<int, int>;
  using vll = vector<ll>;
  vector<vector<pair<int, char> > > graph;
  vector<vi> distance_matrix;

  vi A2;
  // vi desired;
  int GN;
  const ll INF = 1e18;
  const int INF2 = 5e8;
  int dx[]={0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
  template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
  template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
  template<class T> void debug(T a, T b) { for (; a != b; ++a) cerr << *a << ' '; cerr << endl;}
  template<class T> T square(const T& x) { return x * x; }



  void dfs(int v, vi& path, vector<bool>& visited) {
    visited[v] = true;
    path.push_back(v);
    for (auto u : graph[v]) {
      int to = u.first;
      if (!visited[to]) {
        dfs(to, path, visited);
        // path.push_back(v);
      }
    }
  }
  vi create_path(int s) {
    vector<bool> visited(GN);
    vi path;
    dfs(s, path, visited);
    return path;
  }

  ll calc_score(const vi& ar) {
    ll score = 0;
    for (int i = 0; i < GN; ++i) {
      for (auto e: graph[i]) {
        int to = e.first;
        score += square(ar[i] - ar[to]);
      }
    }
    return score;
  }

  void create_distance_matrix() {
    distance_matrix.resize(GN, vi(GN, INF2));
    for (int i = 0; i < GN; ++i) {
      queue<int> q;
      distance_matrix[i][i] = 0;
      q.push(i);
      while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto e : graph[v]) {
          int u = e.first;
          if (distance_matrix[i][u] == INF2) {
            distance_matrix[i][u] = distance_matrix[i][v] + 1;
            q.push(u);
          }
        }
      }
    }
  }
  vi get_path(int s, int t) {
    vi path;
    int dist = distance_matrix[s][t];
    while (s != t) {
      path.push_back(t);
      bool found = false;
      for (auto e : graph[t]) {
        if (distance_matrix[s][e.first] == dist - 1) {
          t = e.first;
          found = true;
          break;
        }
      }
      assert(found);
      --dist;
    }
    path.push_back(s);
    reverse(path.begin(), path.end());
    return path;
  }


  void main_hog() {
    GN = N * N;
    dump(GN);
    graph.resize(GN);
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        A2.push_back(A[i][j]);
        if (j < N-1 && !V[i][j]) {
          graph[i * N + j].push_back({i * N + j + 1, 'R'});
          graph[i * N + j + 1].push_back({i * N + j, 'L'});
        }
        if (i < N-1 && !H[i][j]) {
          graph[i * N + j].push_back({(i + 1) * N + j, 'D'});
          graph[(i + 1) * N + j].push_back({i * N + j, 'U'});
        }
      }
    }
    assert(A2.size() == GN);
    ll orig_score = calc_score(A2);
    dump(orig_score);
    for (int i = 0; i < GN; ++i) assert(graph[i].size() <= 4);
    create_distance_matrix();
    vi path = create_path(0);
    const int M = path.size();
    assert(M==GN);
    dump(M);
    vector<pii> moves;
    vi A3 = A2;
    int block = M / 2, thr;
    int i = 0, j = block;
    while (moves.size() <= 4 * GN && block > 2) {
      thr = block;
      int cnt = 0;
      i = 0;
      j = block;
      dump(i);dump(j);dump(block);

      while (j < M) { // todo: fix boundary
        chmax(j, i+1);
        if (j >= M) break;
        if (cnt >= block) {
          thr += block * 2;
          cnt -= block * 2;
        }
        if (A2[path[i]] >= thr && A2[path[j]] < thr) {
          assert(i < GN); assert(j < GN);
          assert(path[i] < GN);
          assert(path[j] < GN);
          dump(i);dump(j);dump(path[i]);dump(path[j]);
          swap(A2[path[i]], A2[path[j]]);
          moves.push_back({path[i], path[j]});
          ++i;++j;++cnt;
        }else if (A2[path[i]] >= thr) {
          ++j;
        } else if (A2[path[j]] < thr) {
          ++i;++cnt;
        } else {
          ++i;++j;++cnt;
        }
      }
      dump(i);
      assert(j==GN);
      block /= 2;
      i = GN - block-1;
      j = GN - 1;
      thr = GN - block;
      cnt = 0;
      while (true) {
        chmin(i, j-1);
        if (i < 0) break;
        dump(i);dump(j);
        if (cnt >= block) {
          thr -= block * 2;
          cnt -= block * 2;
        }
        if (A2[path[i]] >= thr && A2[path[j]] < thr) {
          moves.push_back({path[i], path[j]});
          swap(A2[path[i]], A2[path[j]]);
          --i;--j;++cnt;
        } else if (A2[path[i]] >= thr) {
          --j;++cnt;
        } else if (A2[path[j]] < thr) {
          --i;
        } else {
          --i;--j;++cnt;
        }
      }
      assert(i==-1);
      block /= 2;
    }
    moves.resize(4 * GN);

    // output
    auto ps1 = moves[0].first, ps2 = moves[0].second;

    printf("%d %d %d %d\n", ps1 / N, ps1 % N, ps2 / N, ps2 % N);
    auto get_command=[&](int p1, int p2) {
      if (p1 == p2) return '.';
      for (int i = 0; i < graph[p1].size(); ++i) {
        if (graph[p1][i].first == p2) return graph[p1][i].second;
      }
      assert(false);
      return 'X';
    };
    vector<tuple<bool, char, char> > ans;
    for (int i = 0; i < moves.size() && ans.size() < 4 * GN; ++i) {
      auto [p1, p2] = moves[i];
      dump(p1);dump(p2);

      bool is_swap =true;
      // if (A2[p1] > A2[p2]) {
      //   is_swap = true;
      //   swap(A2[p1], A2[p2]);
      // }
      assert(is_swap);
      swap(A3[p1], A3[p2]);
      if (i + 1 >= moves.size()) {
        ans.push_back({is_swap, '.', '.'});
      } else {
        auto [p1n, p2n] = moves[i + 1];
        auto path1 = get_path(p1, p1n), path2 = get_path(p2, p2n);
        assert(!path1.empty());
        assert(!path2.empty());
        for (int j = 0; j + 1 < max(path1.size(), path2.size()); ++j) {
          if (j + 1 >= path1.size()) path1.push_back(path1.back());
          if (j + 1 >= path2.size()) path2.push_back(path2.back());
          ans.push_back({is_swap, get_command(path1[j], path1[j+1]), get_command(path2[j], path2[j+1])});
          is_swap = false;
        }
      }
    }
    ans.resize(4 * GN);
    ll new_score = calc_score(A3);
    dump(orig_score);dump(new_score);
    dump(log((orig_score / (double)new_score)) / log(2.0));
    for (auto a: ans) {
      auto [is_swap, c1, c2] = a;
      printf("%d %c %c\n", (int)is_swap, c1, c2);
    }
  }
}; // namespace hog

void parse_input() {
	string line;
	cin >> T >> N;
	V.resize(N);
	for (int i = 0; i < N; i++) {
		V[i].resize(N - 1);
		cin >> line;
		for (int j = 0; j < N - 1; j++) {
			V[i][j] = line[j] == '1';
		}
	}
	H.resize(N - 1);
	for (int i = 0; i < N - 1; i++) {
		H[i].resize(N);
		cin >> line;
		for (int j = 0; j < N; j++) {
			H[i][j] = line[j] == '1';
		}
	}
	A.resize(N);
	for (int i = 0; i < N; i++) {
		A[i].resize(N);
		for (int j = 0; j < N; j++) {
			cin >> A[i][j];
		}
	}
}

int main() {
	parse_input();
  if (T <= 1) asi1024::solve();
  else if (T == 15) hog::main_hog();
  else ats5515::solve();
	// cout << "0 0 0 0" << std::endl;
}

Submission Info

Compile Error

Main.cpp: In function ‘std::vector<std::tuple<int, char, char> > asi1024::beam_search(int, int, int, int)’:
Main.cpp:585:30: warning: comparison of integer expressions of different signedness: ‘std::vector<asi1024::State>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  585 |     if (sorted_states.size() > BEAM_WIDTH) sorted_states.resize(BEAM_WIDTH);
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/12/cassert:44,
                 from Main.cpp:3:
Main.cpp: In function ‘void hog::main_hog()’:
Main.cpp:758:22: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  758 |     assert(A2.size() == GN);
      |            ~~~~~~~~~~^~~~~
Main.cpp:771:25: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  771 |     while (moves.size() <= 4 * GN && block > 2) {
      |            ~~~~~~~~~~~~~^~~~~~~~~
Main.cpp: In lambda function:
Main.cpp:839:25: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, char> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  839 |       for (int i = 0; i < graph[p1].size(); ++i) {
      |                       ~~^~~~~~~~~~~~~~~~~~
Main.cpp: In function ‘void hog::main_hog()’:
Main.cpp:846:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  846 |     for (int i = 0; i < moves.size() && ans.size() < 4 * GN; ++i) {
      |                     ~~^~~~~~~~~~~~~~
Main.cpp:846:52: warning: comparison of integer expressions of different signedness: ‘std::vector<std::tuple<bool, char, char> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  846 |     for (int i = 0; i < moves.size() && ans.size() < 4 * GN; ++i) {
      |                                         ~~~~~~~~~~~^~~~~~~~
Main.cpp:857:17: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  857 |       if (i + 1 >= moves.size()) {
      |           ~~~~~~^~~~~~~~~~~~~~~
Main.cpp:864:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘const long unsigned int’ [-Wsign-compare]
  864 |         for (int j = 0; j + 1 < max(path1.size(), path2.size()); ++j) {
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:865:21: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  865 |           if (j + 1 >= path1.size()) path1.push_back(path1.back());
      |               ~~~~~~^~~~~~~~~~~~~~~
Main.cpp:866:21: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  866 |           if (j + 1 >= path2.size()) path2.push_back(path2.back());
      |               ~~~~~~^~~~~~~~~~~~~~~

Judge Result