#include using namespace std; /* -------------------------------------------------------------------------- * Grid XOR Maximisation - 2‑phase solver (Random search → SA) * 固定長版:コピーセル数 = MAX_CHOOSE に固定 * • pos の長さは常に MAX_CHOOSE * • 近傍操作は SWAP / REPLACE のみ(長さは変えない) * -------------------------------------------------------------------------- */ // ---------- utilities ------------------------------------------------------ struct Timer { using Clock = chrono::high_resolution_clock; chrono::time_point st{Clock::now()}; double elapsed() const { return chrono::duration(Clock::now() - st).count(); } }; // ---------- constants ------------------------------------------------------ constexpr int N = 10; constexpr int OP_LIMIT = 1000; constexpr int MAX_CHOOSE = 7; // ← 固定長 constexpr double RAND_PHASE = 1.00; // seconds for pure random search constexpr double TL = 1.98; // total time limit (s) using Board = array, N>; // ---------- state representation ------------------------------------------ struct State { array pos; // fixed‑size array (indices 0..99) vector s; // size MAX_CHOOSE+1, s[0]=0 bitset<100> mask; // copy cell mask long long score = -1; // board score }; // ---------- helpers -------------------------------------------------------- inline bitset<100> make_mask(const array& pos) { bitset<100> bs; for (int v : pos) bs.set(v); return bs; } inline long long eval_board(const vector& s, const Board& A, const bitset<100>& copyMask) { long long sum = 0; for (int idx = 0; idx < 100; ++idx) { int i = idx / N, j = idx % N; if (copyMask.test(idx)) { sum += A[i][j]; } else { uint32_t best = A[i][j]; for (uint32_t v : s) { uint32_t cand = A[i][j] ^ v; if (cand > best) best = cand; } sum += best; } } return sum; } inline void rebuild_prefXor(State& st, const Board& A) { st.s.resize(MAX_CHOOSE + 1); st.s[0] = 0; for (int k = 0; k < MAX_CHOOSE; ++k) { int idx = st.pos[k]; st.s[k + 1] = st.s[k] ^ A[idx / N][idx % N]; } st.mask = make_mask(st.pos); } // ---------- neighbour generator ------------------------------------------- struct Mutator { mt19937 rng; uniform_real_distribution uni{0.0, 1.0}; uniform_int_distribution cellDist{0, 99}; explicit Mutator(uint32_t seed) : rng(seed) {} array random_pos() { array v{}; int filled = 0; while (filled < MAX_CHOOSE) { int x = cellDist(rng); bool dup = false; for (int i = 0; i < filled; ++i) if (v[i] == x) { dup = true; break; } if (!dup) v[filled++] = x; } return v; } // mutate in‑place (SWAP or REPLACE) keeping length constant void mutate(array& pos) { double r = uni(rng); if (r < 0.5) { // SWAP uniform_int_distribution d(0, MAX_CHOOSE - 1); int a = d(rng), b = d(rng); if (a != b) swap(pos[a], pos[b]); } else { // REPLACE one element with unused cell uniform_int_distribution d(0, MAX_CHOOSE - 1); int idx = d(rng); for (int t = 0; t < 20; ++t) { int x = cellDist(rng); bool dup = false; for (int v : pos) if (v == x) { dup = true; break; } if (!dup) { pos[idx] = x; break; } } } } }; // ---------- random search -------------------------------------------------- State random_search(const Board& A, Timer& timer, Mutator& mut) { State best; best.score = -1; while (timer.elapsed() < RAND_PHASE) { State st; st.pos = mut.random_pos(); rebuild_prefXor(st, A); st.score = eval_board(st.s, A, st.mask); if (st.score > best.score) best = st; } return best; } // ---------- simulated annealing ------------------------------------------- State simulated_annealing(const Board& A, State init, Timer& timer, Mutator& mut) { State cur = init, best = cur; constexpr double T0 = 1e5, Tend = 1.0; while (true) { double t = timer.elapsed(); if (t >= TL) break; double temp = T0 * pow(Tend / T0, (t - RAND_PHASE) / (TL - RAND_PHASE)); State nxt = cur; mut.mutate(nxt.pos); rebuild_prefXor(nxt, A); nxt.score = eval_board(nxt.s, A, nxt.mask); long long diff = nxt.score - cur.score; if (diff >= 0 || mut.uni(mut.rng) < exp(double(diff) / temp)) { cur = nxt; if (cur.score > best.score) best = cur; } } return best; } // ---------- operation sequence builder ------------------------------------ vector build_ops(const State& best, const Board& A) { const vector& pref = best.s; const bitset<100>& mask = best.mask; array, N> idx{}; for (auto& r : idx) r.fill(-1); for (int cell = 0; cell < 100; ++cell) { if (mask.test(cell)) continue; int i = cell / N, j = cell % N; int best_k = 0; uint32_t best_val = A[i][j]; for (int k = 1; k <= MAX_CHOOSE; ++k) { uint32_t cand = A[i][j] ^ pref[k]; if (cand > best_val) { best_val = cand; best_k = k; } } idx[i][j] = best_k; } vector ops; ops.reserve(OP_LIMIT); auto push=[&](char c){ if((int)ops.size() 0) { for (int row = 0; row < N; ++row) { for (int k = 0; k < N; ++k) { int col = (row % 2 == 0) ? k : (N - 1 - k); if (idx[row][col] == phase) push('W'); if (k != N - 1) push(row % 2 ? 'L' : 'R'); } if (row != N - 1) push('D'); } if (phase == MAX_CHOOSE) break; } int tgt = best.pos[phase]; int tx = tgt / N, ty = tgt % N; if (phase == 0) { for (int d = 0; d < tx; ++d) push('D'); } else { for (int d = N - 1; d > tx; --d) push('U'); } for (int d = 0; d < ty; ++d) push('R'); push('C'); for (int d = ty; d > 0; --d) push('L'); for (int d = tx; d > 0; --d) push('U'); } if ((int)ops.size() > OP_LIMIT) ops.resize(OP_LIMIT); return ops; } // ---------- main ----------------------------------------------------------- int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n_in, t_in; if (!(cin >> n_in >> t_in)) return 0; Board A{}; for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> A[i][j]; Timer timer; Mutator mut(123456789u); State init = random_search(A, timer, mut); State best = simulated_annealing(A, init, timer, mut); auto ops = build_ops(best, A); for (char c : ops) cout << c << '\n'; }