結果
問題 |
No.5022 XOR Printer
|
ユーザー |
|
提出日時 | 2025-07-26 16:58:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,923 ms / 2,000 ms |
コード長 | 5,764 bytes |
コンパイル時間 | 3,579 ms |
コンパイル使用メモリ | 297,140 KB |
実行使用メモリ | 7,716 KB |
スコア | 5,170,297,161 |
最終ジャッジ日時 | 2025-07-26 17:03:38 |
合計ジャッジ時間 | 103,462 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
// 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 <bits/stdc++.h> using namespace std; struct Input { int N, T; vector<vector<long long>> 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<long long> 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<long long,string> run_once(const Input& in, mt19937& rng){ const int D = 4; State st; st.N = in.N; st.limit = min(in.T, 1000); st.grid.resize(in.N*in.N); for(int i=0;i<in.N;i++) for(int j=0;j<in.N;j++){ st.grid[st.idx(i,j)] = in.grid[i][j]; st.score += in.grid[i][j]; } st.ops.reserve(st.limit); int cells = in.N * in.N; vector<int> budget(cells, 8); int leftover = st.limit - 8*cells; if(leftover < 0) leftover = 0; uniform_int_distribution<int> distCell(0, cells-1); while(leftover > 0){ int id = distCell(rng); if(budget[id] < 13){ budget[id]++; leftover--; } } vector<Pos> path; path.reserve(cells); for(int r=0;r<in.N;r++){ if(r%2==0){ for(int c=0;c<in.N;c++) path.push_back({r,c}); }else{ for(int c=in.N-1;c>=0;c--) path.push_back({r,c}); } } auto inside=[&](int r,int c){return 0<=r && r<in.N && 0<=c && c<in.N;}; for(size_t idx=0; idx<path.size(); ++idx){ Pos x = path[idx]; int mvTo = dist(st.cur, x); if((int)st.ops.size() + mvTo + 1 > 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())+1; 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<Pos> 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<cells.size();i++) for(size_t j=i+1;j<cells.size();j++){ Pos a=cells[i], b=cells[j]; int c2 = dist(x,a) + dist(a,b) + dist(b,x) + 3; if(c2 > 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<long long,string> 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<double>(chrono::steady_clock::now()-start).count() < 1.92); 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<long long>(in.N)); for(int i=0;i<in.N;i++) for(int j=0;j<in.N;j++) cin>>in.grid[i][j]; auto [score, out] = solve(in); cout<<out<<"\n"; cerr<<score<<"\n"; return 0; }