// Baseline Score: 1518598366 // Improved Score: 1542584325 // Improvement: 23985959 // XOR Printer greedy solver prepared for beam search. // Randomly allocate 7-13 turns to each of the 100 cells and traverse them in // snake order. For each cell, greedily select up to two assist cells within // distance d(=3) whose total cost does not exceed the allocated budget. Repeat // the whole process while time allows and output the best sequence found using // newline separated operations. #include using namespace std; struct Input { int N, T; vector> grid; }; struct Pos {int r, c;}; inline int dist(const Pos& a, const Pos& b){ return abs(a.r - b.r) + abs(a.c - b.c); } struct State { int N, limit; vector grid; // flattened N*N Pos cur{0,0}; long long s = 0; long long score = 0; string ops; int idx(int r,int c) const { return r*N + c; } }; void move_to(State& st, Pos to){ while(st.cur.r < to.r){ st.ops += 'D'; st.cur.r++; } while(st.cur.r > to.r){ st.ops += 'U'; st.cur.r--; } while(st.cur.c < to.c){ st.ops += 'R'; st.cur.c++; } while(st.cur.c > to.c){ st.ops += 'L'; st.cur.c--; } } void apply_C(State& st){ st.s ^= st.grid[st.idx(st.cur.r, st.cur.c)]; st.ops += 'C'; } void apply_W(State& st){ int id = st.idx(st.cur.r, st.cur.c); st.score -= st.grid[id]; st.grid[id] ^= st.s; st.score += st.grid[id]; st.ops += 'W'; } pair run_once(const Input& in, mt19937& rng){ const int D = 3; State st; st.N = in.N; st.limit = min(in.T, 1000); st.grid.resize(in.N*in.N); for(int i=0;i budget(cells, 7); int leftover = st.limit - 7*cells; if(leftover < 0) leftover = 0; uniform_int_distribution distCell(0, cells-1); while(leftover > 0){ int id = distCell(rng); if(budget[id] < 13){ budget[id]++; leftover--; } } vector path; path.reserve(cells); for(int r=0;r=0;c--) path.push_back({r,c}); } } auto inside=[&](int r,int c){return 0<=r && r st.limit) break; // need at least W move_to(st, x); int xid = st.idx(x.r, x.c); int cellRemain = min(budget[idx], st.limit - (int)st.ops.size()); long long bestVal = st.grid[xid] ^ st.s; // no assist int bestType = 0; // 0 none,1 one,2 two Pos bestA,bestB; int bestCost=1; long long bestS=st.s; vector cells; for(int dr=-D; dr<=D; dr++) for(int dc=-D; dc<=D; dc++) if(abs(dr)+abs(dc)<=D && inside(x.r+dr,x.c+dc)) cells.push_back({x.r+dr,x.c+dc}); for(auto a: cells){ int c1 = dist(x,a)*2 + 2 + 0; // includes C and W if(c1 > cellRemain) continue; long long ns = st.s ^ st.grid[st.idx(a.r,a.c)]; long long val = st.grid[xid] ^ ns; if(val > bestVal){ bestVal = val; bestType=1; bestA=a; bestCost=c1; bestS=ns; } } for(size_t i=0;i cellRemain) continue; long long ns = st.s ^ st.grid[st.idx(a.r,a.c)] ^ st.grid[st.idx(b.r,b.c)]; long long val = st.grid[xid] ^ ns; if(val > bestVal){ bestVal = val; bestType=2; bestA=a; bestB=b; bestCost=c2; bestS=ns; } } if(bestType==0){ apply_W(st); // cost 1 already ensured }else if((int)st.ops.size() + bestCost <= st.limit){ if(bestType==1){ move_to(st,bestA); apply_C(st); move_to(st,x); apply_W(st); }else{ move_to(st,bestA); apply_C(st); move_to(st,bestB); apply_C(st); move_to(st,x); apply_W(st); } st.s = bestS; } if(idx+1 >= path.size()) break; Pos nxt = path[idx+1]; int mv = dist(st.cur, nxt); if((int)st.ops.size()+mv > st.limit) break; move_to(st, nxt); } string out; out.reserve(st.ops.size()*2); for(char c: st.ops){ out.push_back(c); out.push_back('\n'); } if(!out.empty()) out.pop_back(); return {st.score, out}; } pair solve(const Input& in){ mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); auto start = chrono::steady_clock::now(); long long bestScore = -1; string bestOps; int loops=0; do{ auto [sc,ops] = run_once(in, rng); if(sc > bestScore){ bestScore = sc; bestOps = std::move(ops); } loops++; }while(chrono::duration(chrono::steady_clock::now()-start).count() < 1.8); cerr << bestScore << "\n"; cerr << loops << "\n"; return {bestScore, bestOps}; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); Input in; if(!(cin>>in.N>>in.T)) return 0; in.grid.assign(in.N, vector(in.N)); for(int i=0;i>in.grid[i][j]; auto [score, out] = solve(in); cout<