#include using namespace std; /* -------------------------------------------------------------------------- * Grid XOR Maximisation – 2‑phase solver (Random search → SA) * 2025‑07‑26 update: * • pos 長さ固定 (MAX_CHOOSE) * • ルート生成を “常にマンハッタン最短経路” に変更 * ‑ 各フェーズごとに "今いるマス→最近傍の書き込み対象" を * 貪欲に訪問して W * ‑ コピーセルへの移動もマンハッタン一直線 * • ヘビ走査を廃止し、移動手数を大幅削減 * -------------------------------------------------------------------------- */ // ---------- 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 = 15; constexpr double RAND_PHASE = 1.00; // s constexpr double TL = 1.98; // s total using Board = array, N>; // ---------- state ---------------------------------------------------------- struct State { array pos; // copy cells (0..99) vector s; // prefix XOR size MAX_CHOOSE+1 bitset<100> mask; // copy mask long long score = -1; }; // ---------- evaluation 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 uni{0.0,1.0}; uniform_int_distribution cellDist{0,99}; explicit Mutator(uint32_t seed):rng(seed){} array random_pos(){ array v{}; int f=0; while(f& pos){ if(uni(rng)<0.5){ // swap uniform_int_distributiond(0,MAX_CHOOSE-1); int a=d(rng),b=d(rng); if(a!=b) swap(pos[a],pos[b]); }else{ // replace uniform_int_distributiond(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 + SA ---------------------------------------------------- State random_search(const Board&A,Timer&timer,Mutator&mut){ State best; best.score=-1; while(timer.elapsed()best.score) best=st;} return best; } 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)best.score) best=cur; } } return best; } // ---------- shortest‑path based operation builder -------------------------- vector build_ops(const State& best,const Board&A){ const vector&pref=best.s; const bitset<100>&mask=best.mask; // Prepare write target lists per phase (1..MAX_CHOOSE) array>,MAX_CHOOSE+1> targets; // index by phase for(int idx=0;idx<100;++idx){ if(mask.test(idx)) continue; int i=idx/ N,j=idx%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;} } targets[best_k].push_back({i,j}); } vector ops; ops.reserve(OP_LIMIT); auto push=[&](char c){ ops.push_back(c); }; auto move_line=[&](int& cx,int& cy,int tx,int ty){ // Manhattan path (vertical first) while(cxtx){ push('U'); --cx; } while(cyty){ push('L'); --cy; } }; int cx=0,cy=0; // current pos // Phases 0..MAX_CHOOSE (phase0 only move to first copy cell) for(int phase=0;phase<=MAX_CHOOSE;++phase){ if(phase>0){ auto&vec=targets[phase]; while(!vec.empty()){ // nearest greedy int bestIdx=0,bestDist=1e9; for(int i=0;i<(int)vec.size();++i){ int d=abs(cx-vec[i].first)+abs(cy-vec[i].second); if(dOP_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>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<