#1106694 (C++23) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: prussian_coder
• 提出日時: 2025-07-25 11:44:46
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,457 ms / 2,000 ms
• コード長: 31,948 bytes
• コンパイル時間: 5,594 ms
• コンパイル使用メモリ: 261,716 KB
• 実行使用メモリ: 318,208 KB
• スコア: 5,227,012,591
• 最終ジャッジ日時: 2025-07-26 12:45:11
• 合計ジャッジ時間: 73,542 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
other	AC * 50

ソースコード

#pragma GCC optimize "-O3,omit-frame-pointer,inline,unroll-all-loops,fast-math"

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <random>
#include <limits>
#include <cmath>
#include <numeric>
#include <optional>
#include <iterator>
#include <unordered_set>
#include <functional>

using namespace std;

// Random number generator with fixed seed
static mt19937 rng(0);
static uniform_real_distribution<double> uniDist(0.0, 1.0);

// Constants
constexpr int MAX_BIT             = 20;
constexpr int MAX_SEE_BIT         = 4;
constexpr int DEFAULT_TARGET_BIT  = 19;
constexpr double ANNEALING_DECAY  = 0.99;
constexpr double INITIAL_ACCEPT_PROB = 0.8;
constexpr int BEAM_WIDTH          = 10;
constexpr int MAX_TRIAL           = 20;
constexpr int MAX_TRIAL_LAST      = 50;
constexpr int MIN_TARGET_BIT      = 11; // Use beam search below this

// Global variables
int N, T, N2;
vector<int> board;
vector<int> BINARY_VALS;
int BIT_MASK;

// Forward declarations used by beam search
int manhattan_distance(int pos1, int pos2);
vector<char> generate_move_commands(int start, int end);

//------------------------------------------------------------------------------
// Utility Functions
//------------------------------------------------------------------------------

// 1次元の位置を(x, y)に変換
pair<int, int> to_2d(int pos) {
    return { pos / N, pos % N };
}

inline void for_each_near(int pos, const function<void(int)>& f) {
    auto [x, y] = to_2d(pos);
    for (int dx = -8; dx <= 8; ++dx) {
        int nx = x + dx;
        if (nx < 0 || nx >= N) continue;
        int rem = 8 - abs(dx);
        for (int dy = -rem; dy <= rem; ++dy) {
            int ny = y + dy;
            if (ny < 0 || ny >= N) continue;
            f(nx * N + ny);
        }
    }
}


//------------------------------------------------------------------------------
// Beam search borrowed from sol7.cpp (simplified for reuse)
//------------------------------------------------------------------------------

struct BeamState {
    vector<int> board;
    int s, pos, turn, score, prev_c_cnt;
    BeamState* prev_state;
    pair<char,int> prev_action;
    BeamState(
        const vector<int>& b,
        int st,
        int p,
        int t,
        int sc
    ) : board(b), s(st), pos(p), turn(t), score(sc), prev_c_cnt(0),
        prev_state(nullptr), prev_action({'?',0}) {}
};

inline bool beam_state_valid(const BeamState* st, int limit) {
    if (st->turn == limit) return true;
    int mask = (1 << 19) - 1;
    for (int v : st->board) {
        mask &= v;
        if (mask == 0) return true;
    }
    return false;
}

inline int beam_last_score(const BeamState* st, int limit) {
    int min_v = numeric_limits<int>::max();
    int min_pos = 0;
    for (int i = 0; i < N2; ++i) {
        if (st->board[i] < min_v) {
            min_v = st->board[i];
            min_pos = i;
        }
    }
    int dist = manhattan_distance(st->pos, min_pos);
    if (st->turn + dist + 3 >= limit) return 0;
    return st->score + st->s - min_v;
}

inline vector<char> beam_last_move(const BeamState* st) {
    int min_v = numeric_limits<int>::max();
    int min_pos = 0;
    for (int i = 0; i < N2; ++i) {
        if (st->board[i] < min_v) {
            min_v = st->board[i];
            min_pos = i;
        }
    }
    auto cmds = generate_move_commands(st->pos, min_pos);
    cmds.push_back('W');
    cmds.push_back('C');
    cmds.push_back('W');
    return cmds;
}

class BeamSearchSolver {
    static const int BEAM_WIDTH = 80;
    static const int STATE_QUE_SIZE = 10;
    int limit;
    struct PairHash { size_t operator()(uint64_t x) const { return x; } };

public:
    explicit BeamSearchSolver(int lim) : limit(lim) {}

    BeamState* process(const vector<int>& init_board, int init_s, int init_pos) {
        static BeamState* states[STATE_QUE_SIZE][BEAM_WIDTH];
        static int sizes[STATE_QUE_SIZE];
        for (int i = 0; i < STATE_QUE_SIZE; ++i) sizes[i] = 0;

        auto cmp = [](BeamState* a, BeamState* b) { return a->score > b->score; };

        BeamState* initial = new BeamState(
            init_board, init_s, init_pos, 0,
            accumulate(init_board.begin(), init_board.end(), 0)
        );
        states[0][0] = initial;
        sizes[0] = 1;
        push_heap(&states[0][0], &states[0][0] + 1, cmp);

        int best_score = 0;
        BeamState* best_state = nullptr;

        for (int turn = 0; turn < limit; ++turn) {
            int idx = turn % STATE_QUE_SIZE;
            int cur_sz = sizes[idx];
            BeamState* cur[BEAM_WIDTH];
            for (int i = 0; i < cur_sz; ++i) cur[i] = states[idx][i];
            sizes[idx] = 0;

            unordered_set<uint64_t, PairHash> seen;
            for (int i = 0; i < cur_sz; ++i) {
                BeamState* st = cur[i];
                uint64_t key = (uint64_t(st->score) << 16) | uint32_t(st->s/1024);
                if (!seen.insert(key).second) continue;
                for_each_near(st->pos, [&](int v2) {
                    try_push(st, 'W', v2, states, sizes, cmp);
                    if (st->prev_c_cnt < 2)
                        try_push(st, 'C', v2, states, sizes, cmp);
                });
            }
            for (int i = 0; i < cur_sz; ++i) {
                int fs = beam_last_score(cur[i], limit);
                if (fs > best_score) {
                    best_score = fs;
                    best_state = cur[i];
                }
            }
        }
        return best_state;
    }

private:
    void try_push(
        BeamState* st,
        char key,
        int pos,
        BeamState* states[][BEAM_WIDTH],
        int sizes[],
        const function<bool(BeamState*, BeamState*)>& cmp
    ) {
        int dist = manhattan_distance(st->pos, pos);
        int next_turn = st->turn + dist + 1;
        if (next_turn > limit) return;
        int new_score = (key == 'C') ? st->score
                          : st->score + ((st->board[pos] ^ st->s) - st->board[pos]);
        int idx = next_turn % STATE_QUE_SIZE;
        int sz = sizes[idx];
        if (sz < BEAM_WIDTH) {
            BeamState* ns = apply_move(st, key, pos, next_turn, new_score);
            if (beam_state_valid(ns, limit)) {
                states[idx][sz] = ns;
                ++sizes[idx];
                push_heap(&states[idx][0], &states[idx][sizes[idx]], cmp);
            }
        } else if (new_score > states[idx][0]->score) {
            BeamState* ns = apply_move(st, key, pos, next_turn, new_score);
            if (beam_state_valid(ns, limit)) {
                pop_heap(&states[idx][0], &states[idx][BEAM_WIDTH], cmp);
                states[idx][BEAM_WIDTH - 1] = ns;
                push_heap(&states[idx][0], &states[idx][BEAM_WIDTH], cmp);
            }
        }
    }

    BeamState* apply_move(
        BeamState* st,
        char key,
        int pos,
        int next_turn,
        int new_score
    ) {
        BeamState* ns = new BeamState(*st);
        ns->prev_state = st;
        ns->prev_action = {key, st->pos};
        ns->turn = next_turn;
        ns->score = new_score;
        if (key == 'C') {
            ns->s ^= st->board[pos];
            ns->prev_c_cnt = st->prev_c_cnt + 1;
        } else {
            ns->board[pos] = st->board[pos] ^ st->s;
            ns->prev_c_cnt = 0;
        }
        ns->pos = pos;
        return ns;
    }
};

vector<char> run_beam_search(
    const vector<int>& init_board,
    int init_s,
    int init_pos,
    int rem_turn
) {
    BeamSearchSolver solver(rem_turn);
    BeamState* best = solver.process(init_board, init_s, init_pos);
    vector<char> last_actions = beam_last_move(best);
    vector<char> actions;
    for (BeamState* cur = best; cur->prev_state != nullptr; cur = cur->prev_state) {
        auto [key, last_pos] = cur->prev_action;
        actions.push_back(key);
        auto mv = generate_move_commands(last_pos, cur->pos);
        for (auto it = mv.rbegin(); it != mv.rend(); ++it) actions.push_back(*it);
    }
    reverse(actions.begin(), actions.end());
    actions.insert(actions.end(), last_actions.begin(), last_actions.end());
    return actions;
}

// (x, y)座標を1次元インデックスへ変換
int to_1d(int x, int y) {
    return x * N + y;
}

// マンハッタン距離を求める
int manhattan_distance(int pos1, int pos2) {
    auto [x1, y1] = to_2d(pos1);
    auto [x2, y2] = to_2d(pos2);
    return abs(x1 - x2) + abs(y1 - y2);
}

// startからendまで移動する操作列を生成
vector<char> generate_move_commands(int start, int end) {
    vector<char> commands;
    auto [x1, y1] = to_2d(start);
    auto [x2, y2] = to_2d(end);
    int cx = x1;
    int cy = y1;

    // Vertical moves
    while (cx < x2) { commands.push_back('D'); ++cx; }
    while (cx > x2) { commands.push_back('U'); --cx; }

    // Horizontal moves
    while (cy < y2) { commands.push_back('R'); ++cy; }
    while (cy > y2) { commands.push_back('L'); --cy; }

    return commands;
}

// 移動操作列をコマンドベクタへ追加するヘルパー
void append_move_commands(vector<char>& out, int start, int end) {
    auto mv = generate_move_commands(start, end);
    out.insert(out.end(), mv.begin(), mv.end());
}

// 操作列を順に適用しボードと状態を更新
void process_board(
    vector<int>& b,
    const vector<char>& commands,
    int& s,
    int& pos
) {
    for (char c : commands) {
        switch (c) {
            case 'W': b[pos] ^= s;   break;
            case 'C': s ^= b[pos];   break;
            case 'D': pos += N;      break;
            case 'U': pos -= N;      break;
            case 'R': pos += 1;      break;
            case 'L': pos -= 1;      break;
        }
    }
}

// process_board の逆操作を一手だけ行う
void revert_board(
    vector<int>& b,
    char c,
    int& s,
    int& pos
) {
    switch (c) {
        case 'W': b[pos] ^= s;   break;
        case 'C': s ^= b[pos];   break;
        case 'D': pos -= N;      break;
        case 'U': pos += N;      break;
        case 'R': pos -= 1;      break;
        case 'L': pos += 1;      break;
    }
}

// start_pos と end_pos を含む長方形領域内の中間点を列挙
vector<int> get_one_intermediate_positions_2d(
    int start_pos,
    int end_pos
) {
    auto [sx, sy] = to_2d(start_pos);
    auto [ex, ey] = to_2d(end_pos);

    if (sx > ex) swap(sx, ex);
    if (sy > ey) swap(sy, ey);

    vector<int> candidates;
    for (int x = sx; x <= ex; ++x) {
        for (int y = sy; y <= ey; ++y) {
            if (x != ex || y != ey) {
                candidates.push_back(to_1d(x, y));
            }
        }
    }
    return candidates;
}

// 1次元移動において2点の中間候補を取得
vector<pair<int, int>> get_two_intermediate_positions_1d(
    int start,
    int end
) {
    int left, right;
    if (start <= end) {
        left  = start;
        right = end;
    } else {
        left  = -start;
        right = -end;
    }

    vector<pair<int,int>> result;
    for (int m1 = left; m1 <= right; ++m1) {
        for (int m2 = m1; m2 <= right; ++m2) {
            result.emplace_back(abs(m1), abs(m2));
        }
    }
    return result;
}

// 2次元移動で経由しうる2点の組み合わせを取得
vector<pair<int, int>> get_two_intermediate_positions_2d(
    int start_pos,
    int end_pos
) {
    auto [sx, sy] = to_2d(start_pos);
    auto [ex, ey] = to_2d(end_pos);

    auto x_pairs = get_two_intermediate_positions_1d(sx, ex);
    auto y_pairs = get_two_intermediate_positions_1d(sy, ey);

    vector<pair<int,int>> candidates;
    for (auto& xp : x_pairs) {
        for (auto& yp : y_pairs) {
            int pos1 = to_1d(xp.first,  yp.first);
            int pos2 = to_1d(xp.second, yp.second);
            if (pos1 != pos2 && pos2 != end_pos) {
                candidates.emplace_back(pos1, pos2);
            }
        }
    }
    return candidates;
}

// target_bit のビットが目的範囲に収まっているか判定
bool is_valid_state(int state, int target_bit) {
    return (BINARY_VALS[target_bit] <= state &&
            state < BINARY_VALS[target_bit + 1]);
}


//------------------------------------------------------------------------------
// RouteOptimizer: 2-opt 山登り法で経路を改良するクラス
//------------------------------------------------------------------------------
class RouteOptimizer {
public:
    // 与えられた盤面で target_bit が0のマスを巡回する経路を生成
    vector<int> generate_optimal_route(
        int start_pos,
        const vector<int>& brd,
        int target_bit
    ) {
        auto targets = find_target_positions(brd, target_bit);
        auto route   = build_nearest_neighbor_route(
                           start_pos,
                           brd,
                           move(targets),
                           target_bit
                       );

        route = apply_2opt_optimization(move(route), brd, target_bit);

        return route;
    }

private:
    // target_bit が0の位置一覧を取得
    vector<int> find_target_positions(
        const vector<int>& brd,
        int target_bit
    ) {
        vector<int> res;
        res.reserve(N2);
        for (int i = 0; i < N2; ++i) {
            if (target_bit <= 17 && ~(brd[i] >> 18) & 1) {
                continue;
            }
            if (((brd[i] >> target_bit) & 1) == 0) {
                res.push_back(i);
            }
        }
        return res;
    }

    // 貪欲法で近傍を順に訪問する経路を構築
    vector<int> build_nearest_neighbor_route(
        int start_pos,
        const vector<int>& brd,
        vector<int> targets,
        int target_bit
    ) {
        vector<int> route = { start_pos };
        int cur = start_pos;
        unordered_set<int> rem(targets.begin(), targets.end());

        while (!rem.empty()) {
            int best = -1;
            int bd   = numeric_limits<int>::max();
            for (int t : rem) {
                int d = manhattan_distance(cur, t);
                if (d < bd) {
                    bd   = d;
                    best = t;
                }
            }
            route.push_back(best);
            rem.erase(best);
            cur = best;
        }

        adjust_final_position(route, brd, target_bit);
        return route;
    }

    // 最後に回る位置について、target_bitより大きいbit桁が1になるように修正する
    void adjust_final_position(
        vector<int>& route,
        const vector<int>& brd,
        int target_bit
    ) {
        for (int i = (int)route.size() - 1; i >= 0; --i) {
            if (can_be_final_position(
                    brd[route[i]],
                    target_bit
                )) {
                swap(route[i], route.back());
                return;
            }
        }
    }

    // 2-opt 法で経路を改良（山登りベースだが、スコア変化が0の場合は低確率で変更許容する）
    vector<int> apply_2opt_optimization(
        vector<int> route,
        const vector<int>& brd,
        int target_bit
    ) {
        float acc = INITIAL_ACCEPT_PROB;
        int L      = route.size();

        while (true) {
            bool improved = false;
            vector<int> idx(L+1);
            iota(idx.begin(), idx.end(), 0);
            shuffle(idx.begin(), idx.end(), rng);

            for (int a = 1; a < L && !improved; ++a) {
                for (int b = a + 1; b <= L && !improved; ++b) {
                    int i = idx[a];
                    int j = idx[b];
                    if (i > j) swap(i, j);
                    if (i == 0) {
                        continue;
                    }
                    if (!is_valid_2opt_move(route, brd, i, j, target_bit)) {
                        continue;
                    }

                    int delta = calculate_2opt_improvement(
                                    route, i, j
                                );
                    if (delta < 0 ||
                        (delta == 0 && uniDist(rng) < acc)) {
                        reverse(
                            route.begin() + i,
                            route.begin() + j
                        );
                        improved = true;
                    }
                }
            }

            if (!improved) {
                break;
            }

            acc *= ANNEALING_DECAY;
        }
        return route;
    }

    // 終点との整合性を考慮して 2-opt 移動が妥当か判定
    // 終点が最後に回る位置の場合は、target_bitより大きいbit桁が1である必要がある
    bool is_valid_2opt_move(
        const vector<int>& route,
        const vector<int>& brd,
        int i,
        int j,
        int tb
    ) {
        if (j == (int)route.size() &&
            !can_be_final_position(
                brd[route[i]],
                tb
            )) {
            return false;
        }
        return true;
    }

    // 2-opt による距離改善量を計算
    int calculate_2opt_improvement(
        const vector<int>& route,
        int i,
        int j
    ) {
        int L = route.size();
        if (j == L) {
            return manhattan_distance(route[i - 1], route[j - 1]) -
                   manhattan_distance(route[i - 1], route[i]);
        }

        return manhattan_distance(route[i - 1], route[j - 1]) +
               manhattan_distance(route[i], route[j]) -
               manhattan_distance(route[i - 1], route[i]) -
               manhattan_distance(route[j - 1], route[j]);
    }

    // 指定位置を最終地点にできるか判定
    bool can_be_final_position(
        int cell_val,
        int tb
    ) {
        return (tb == DEFAULT_TARGET_BIT) ||
               is_valid_state(cell_val ^ BIT_MASK, tb);
    }
};


//------------------------------------------------------------------------------
// WriteCopyPlanner: 経路に沿った Write/Copy 操作列を動的計画法で構築する
//------------------------------------------------------------------------------
class WriteCopyPlanner {
public:
    // target_bit と探索に用いるビット数を初期化
    WriteCopyPlanner(int tb)
        : target_bit(tb)
        , see_bit(min(tb, MAX_SEE_BIT))
    {}

    // target_bit未満の上位see_bit桁について、上位から連続して1が立っている数を数える
    // Write操作をした際に、target_bit未満の次のbitが1であれば、次のbitを見たときに回らなくて済むのでお得であるため
    int count_leading_ones(int v) const {
        int cnt = 0;
        for (int k = see_bit - 1; k >= 0; --k) {
            if (!((v >> k) & 1)) {
                break;
            }
            ++cnt;
        }
        return cnt;
    }

    // prev_pos→p1→p2→posへ移動する際に、移動中の数字p1,p2を2つ使用してsの値を更新できるか判定
    // 2つの数値は、target_bit以上のbit桁が1である必要がある。p1 == prev_posの場合は、p1がp1^sに更新されていることに注意
    optional<int> compute_copy_state(
        int p1,
        int p2,
        int prev_pos,
        int st,
        const vector<int>& brd,
        const vector<int>& tops
    ) const {
        int xor1 = brd[p1] ^ BIT_MASK;
        int xor2 = brd[p2] ^ BIT_MASK;
        if (p1 == prev_pos) {
            if (
                xor2 >= (1 << target_bit) ||
                !is_valid_state(brd[p1] ^ brd[p2], target_bit)
            ) {
                return nullopt;
            }
            return tops[p1] ^ tops[p2];
        }
        if (xor1 >= (1 << target_bit) || xor2 >= (1 << target_bit)) {
            return nullopt;
        }
        return st ^ tops[p1] ^ tops[p2];
    }

    // 経路に沿った最適な Write/Copy コマンド列を生成
    vector<char> generate_execution_plan(
        const vector<int>& route,
        const vector<int>& brd,
        int init_state
    ) {
        int L = route.size();
        int S = 1 << see_bit;

        // DP tables
        vector<vector<float>> dp(
            L - 1,
            vector<float>(S, numeric_limits<float>::infinity())
        );

        // 復元目的のためにどこから来たかを記録する
        vector<vector<tuple<int,int,int>>> tr(
            L - 1,
            vector<tuple<int,int,int>>(S, { -1, -1, -1 })
        );

        // 最初のcopy操作について、どのセルを使用したかを記録しておく
        vector<int> start_pos(S, -1);
        int sp = route[0];

        // 現在の地点付近のセルを訪問・コピーし、sのtarget_bitより大きい桁を0、target_bitを1になるようにする
        for (int p = 0; p < N2; ++p) {
            int xor_val = brd[p] ^ init_state;
            if (!is_valid_state(xor_val, target_bit)) continue;

            int st =
                (xor_val % (1 << target_bit)) >>
                (target_bit - see_bit);

            int dist =
                manhattan_distance(sp, p) +
                manhattan_distance(p, route[1]);

            if (dp[0][st] > dist) {
                dp[0][st]        = dist;
                start_pos[st]    = p;
            }
        }

        // target_bit未満の上位see_bit桁のみDPで考慮する
        vector<int> tops(N2);
        for (int i = 0; i < N2; ++i) {
            tops[i] =
                (brd[i] % (1 << target_bit)) >>
                (target_bit - see_bit);
        }

        // DPテーブルを埋める（最終ターンは除く）
        for (int i = 1; i < L - 1; ++i) {
            for (int st = 0; st < S; ++st) {
                if (dp[i - 1][st] == numeric_limits<float>::infinity()) {
                    continue;
                }

                // Copy操作せずに移動する場合
                {
                    int val = tops[route[i]] ^ st;
                    int score = count_leading_ones(val);

                    float cost = dp[i - 1][st] - score;

                    if (dp[i][st] > cost) {
                        dp[i][st]            = cost;
                        tr[i][st]             = { st, -1, -1 };
                    }
                }

                // route[i-1]→p1→p2→route[i]へ移動する際に、途中のp1,p2を2つをCopyしてsを変更する
                if (i > 1) {
                    for (auto& pr :
                         get_two_intermediate_positions_2d(
                             route[i - 1],
                             route[i]
                         )) {
                        auto [p1, p2] = pr;

                        auto ns = compute_copy_state(
                            p1,
                            p2,
                            route[i - 1],
                            st,
                            brd,
                            tops
                        );
                        if (!ns) {
                            continue;
                        }

                        int new_st = *ns;
                        int val    = tops[route[i]] ^ new_st;
                        int score = count_leading_ones(val);

                        float cost = dp[i - 1][st] + 2 - score;

                        if (dp[i][new_st] > cost) {
                            dp[i][new_st]     = cost;
                            tr[i][new_st]      = { st, p1, p2 };
                        }
                    }
                }
            }
        }

        // 経路を復元する
        vector<char> cmds;
        int final_idx = L - 2;
        int best_st   =
            min_element(                  
                dp[final_idx].begin(),  
                dp[final_idx].end()     
            ) - dp[final_idx].begin();

        for (int i = final_idx; i >= 2; --i) {
            auto [prev_st, p1, p2] = tr[i][best_st];
            cmds.push_back('W');

            if (p1 < 0) {
                append_move_commands(cmds, route[i - 1], route[i]);
            } else {
                append_move_commands(cmds, p2, route[i]);
                cmds.push_back('C');

                append_move_commands(cmds, p1, p2);
                cmds.push_back('C');

                append_move_commands(cmds, route[i - 1], p1);
            }

            best_st = prev_st;
        }

        // 最初のcopy操作を追加する

        cmds.push_back('W');
        int init_pos = start_pos[best_st];

        append_move_commands(cmds, init_pos, route[1]);

        cmds.push_back('C');

        append_move_commands(cmds, route[0], init_pos);

        // 経路を逆順にする
        reverse(cmds.begin(), cmds.end());

        // 最後の移動を追加する
        append_move_commands(cmds, route[L - 2], route[L - 1]);

        cmds.push_back(
            (target_bit == DEFAULT_TARGET_BIT) ? 'W' : 'C'
        );

        return cmds;
    }

private:
    int target_bit;
    int see_bit;
};


//------------------------------------------------------------------------------
// State: ビームサーチで保持する盤面・位置・操作列
//------------------------------------------------------------------------------
class State {
public:
    vector<char> commands;
    vector<int> board;
    int s;
    int pos;
    int target_bit;

    // 状態を保持する単純なデータコンテナ
    State(
        const vector<char>& cmds,
        const vector<int>& brd,
        int state,
        int position,
        int tb
    ) : commands(cmds), board(brd), s(state), pos(position), target_bit(tb) {}

    // 現在のボード合計を計算
    int get_score() const {
        return accumulate(board.begin(), board.end(), 0);
    }

    // 処理手数 - target_bit未満のleading_oneの数
    int get_estimated_cost() const {
        int cost = commands.size();
        for (int val : board) {
            for (int b = target_bit - 2; b >= 0; --b) {
                if ((val >> b) & 1) {
                    cost -= 1;
                } else {
                    break;
                }
            }
        }
        return cost;
    }
};



//------------------------------------------------------------------------------
// Postprocess and Main Solver
//------------------------------------------------------------------------------

// このままでは18ビット目が0であるセルが残ってしまうので、操作終了時にこのセルの値とsの値を交換することで、18ビット目が1になるようにしたい
// 操作列 + この処理を加えた操作（移動操作 + C + W + C + W）がT手以下に収まるようにcmdを戻す
void postprocess_board(
    vector<int>& b,
    vector<char>& cmds,
    int& s,
    int& pos
) {
    while (true) {
        int min_pos =
            min_element(b.begin(), b.end()) - b.begin();
        int steps =
            cmds.size() +
            manhattan_distance(pos, min_pos) +
            4;

        if (steps > T) {
            char last_cmd = cmds.back();
            cmds.pop_back();
            revert_board(b, last_cmd, s, pos);
            continue;
        }

        int best_s = numeric_limits<int>::min();
        int best_v = -1;
        for (int v : get_one_intermediate_positions_2d(pos, min_pos)) {
            int s2 = b[v] ^ s;
            if (s2 > best_s) {
                best_s = s2;
                best_v = v;
            }
        }

        if (best_s < 1000000) {
            char last_cmd = cmds.back();
            cmds.pop_back();
            revert_board(b, last_cmd, s, pos);
            continue;
        }

        // 新しい操作列を追加する
        auto mv1 = generate_move_commands(pos, best_v);
        append_move_commands(cmds, pos, best_v);
        cmds.push_back('C');

        auto mv2 = generate_move_commands(best_v, min_pos);
        append_move_commands(cmds, best_v, min_pos);

        cmds.push_back('W');
        cmds.push_back('C');
        cmds.push_back('W');

        vector<char> recent(
            cmds.end() -
            (mv1.size() + 1 + mv2.size() + 3),
            cmds.end()
        );
        process_board(b, recent, s, pos);
        return;
    }
}


// ビームサーチで操作列を生成する
void solve_puzzle() {    
    
    int pos = to_1d(0, 0);
    int s   = 0;
    int trial_count;
    vector<char> cmds;
    vector<State> states = { State(cmds, board, s, pos, MAX_BIT) };

    // 上位bit桁から順に、target_bitより大きい桁が1になるように操作列を生成する
    for (int tb = MAX_BIT - 1; tb >= MIN_TARGET_BIT; --tb) {
        cerr << tb << " " << states[0].commands.size() << endl;
        int last_cmd_size = states[0].commands.size();
        vector<State> next_states;
        for (const auto& state : states) {
            if (last_cmd_size > 930) {
                trial_count = MAX_TRIAL_LAST;
            } else {
                trial_count = MAX_TRIAL;
            }
            for (int trial = 0; trial < trial_count; ++trial) {
                vector<char> commands = state.commands;
                int current_pos = state.pos;
                int current_s = state.s;
                vector<int> current_board = state.board;

                // routeを生成する
                RouteOptimizer ro;
                auto route = ro.generate_optimal_route(current_pos, current_board, tb);

                // 経路に沿った操作列を生成する
                WriteCopyPlanner wcp(tb);
                auto exec_cmds =
                    wcp.generate_execution_plan(route, current_board, current_s);

                // 操作列を適用する
                process_board(current_board, exec_cmds, current_s, current_pos);
                commands.insert(commands.end(), exec_cmds.begin(), exec_cmds.end());
                next_states.emplace_back(commands, current_board, current_s, current_pos, tb);
            }
        }
        if (!next_states.empty() && (int)next_states[0].commands.size() > T){
            states = next_states;
            break;
        };

        // コストが低い順にソートし、上位BEAM_WIDTH個を選抜する
        sort(next_states.begin(), next_states.end(), 
             [](const State& a, const State& b) {
                 return a.get_estimated_cost() < b.get_estimated_cost();
             });

        states.clear();
        int keep_count = min(BEAM_WIDTH, (int)next_states.size());
        for (int i = 0; i < keep_count; ++i) {
            states.push_back(next_states[i]);
        }

    }

    // After main loop, use beam search for remaining turns
    int best_score = 0;
    vector<char> best_cmds;
    for (const auto& state : states) {
        board = state.board;
        cmds = state.commands;
        s = state.s;
        pos = state.pos;

        int remain = T - (int)cmds.size();
        if (remain > 0) {
            auto extra = run_beam_search(board, s, pos, remain);
            process_board(board, extra, s, pos);
            cmds.insert(cmds.end(), extra.begin(), extra.end());
        }

        postprocess_board(board, cmds, s, pos);
        int score = accumulate(board.begin(), board.end(), 0);
        if (score > best_score) {
            best_score = score;
            best_cmds = cmds;
        }
    }

    cmds = best_cmds;
    // 出力
    for (int i = 0; i < T && i < (int)cmds.size(); ++i) {
        cout << cmds[i] << "\n";
    }

}

// 入力を読み込み solve_puzzle を呼び出すエントリポイント
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> T;
    N2 = N * N;
    board.resize(N2);
    for (int i = 0; i < N2; ++i) {
        cin >> board[i];
    }

    BINARY_VALS.resize(MAX_BIT + 1);
    for (int i = 0; i <= MAX_BIT; ++i) {
        BINARY_VALS[i] = 1 << i;
    }

    BIT_MASK = (1 << MAX_BIT) - 1;

    solve_puzzle();
    return 0;
    }