結果
問題 |
No.5022 XOR Printer
|
ユーザー |
|
提出日時 | 2025-07-26 15:26:29 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,331 bytes |
コンパイル時間 | 3,363 ms |
コンパイル使用メモリ | 288,124 KB |
実行使用メモリ | 7,840 KB |
スコア | 2,836,131,724 |
最終ジャッジ日時 | 2025-07-26 15:26:49 |
合計ジャッジ時間 | 5,562 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 WA * 22 |
ソースコード
// baseline score: 0 // improved score: 808204780 // score delta: +808204780 // スネーク順に盤面を巡回し、距離3以内から2マス選んでXORで更新する貪欲解法 #include <bits/stdc++.h> using namespace std; struct Input { int N, T; vector<int> grid; // flattened N*N grid }; struct Result { long long score; string output; }; const int D = 3; // search distance inline void move_to(int &ci, int &cj, int ti, int tj, string &ops, int &steps){ while(ci < ti){ ops += "D\n"; ++ci; ++steps; } while(ci > ti){ ops += "U\n"; --ci; ++steps; } while(cj < tj){ ops += "R\n"; ++cj; ++steps; } while(cj > tj){ ops += "L\n"; --cj; ++steps; } } Result solve(const Input &in){ const int N = in.N; const int T = in.T; vector<int> board = in.grid; // copy auto idx = [&](int x,int y){ return x*N + y; }; vector<pair<int,int>> order; order.reserve(N*N); for(int r=0;r<N;r++){ if(r%2==0){ for(int c=0;c<N;c++) order.emplace_back(r,c); } else{ for(int c=N-1;c>=0;c--) order.emplace_back(r,c); } } int ci=0,cj=0; // current position int s=0; // register int steps=0; string ops; ops.reserve(T); for(auto [x,y] : order){ if(steps >= T) break; // candidate cells within manhattan distance D vector<pair<int,int>> cand; for(int dx=-D; dx<=D; ++dx){ for(int dy=-D; dy<=D; ++dy){ int nx=x+dx, ny=y+dy; if(nx<0||nx>=N||ny<0||ny>=N) continue; if(abs(dx)+abs(dy) > D) continue; cand.emplace_back(nx,ny); } } pair<int,int> best_a = {x,y}; pair<int,int> best_b = {x,y}; int best_val = -1; for(size_t i=0;i<cand.size();++i){ for(size_t j=i;j<cand.size();++j){ int val = board[idx(x,y)] ^ (s ^ board[idx(cand[i].first,cand[i].second)] ^ board[idx(cand[j].first,cand[j].second)]); if(val > best_val){ best_val = val; best_a = cand[i]; best_b = cand[j]; } } } // execute moves and operations move_to(ci,cj,best_a.first,best_a.second,ops,steps); if(steps>=T) break; ops += "C\n"; s ^= board[idx(best_a.first,best_a.second)]; ++steps; if(steps>=T) break; move_to(ci,cj,best_b.first,best_b.second,ops,steps); if(steps>=T) break; ops += "C\n"; s ^= board[idx(best_b.first,best_b.second)]; ++steps; if(steps>=T) break; move_to(ci,cj,x,y,ops,steps); if(steps>=T) break; ops += "W\n"; board[idx(x,y)] ^= s; ++steps; cerr<<"s="<<s<<"(x,y)="<<x<<","<<y<<" v="<<board[idx(x,y)]<<endl; int a=board[idx(best_a.first,best_a.second)]; int b=board[idx(best_b.first,best_b.second)]; int ab=a^b; cerr<<",a"<<a<<",b"<<b<<",a^b"<<ab<<endl; if(steps>=T) break; } // compute score long long total=0; for(int v:board) total+=v; return {total, ops}; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); Input in; if(!(cin>>in.N>>in.T)) return 0; in.grid.resize(in.N*in.N); for(int i=0;i<in.N*in.N;i++) cin>>in.grid[i]; auto res=solve(in); cout<<res.output; cerr<<res.score<<"\n"; return 0; }