結果

問題 No.5022 XOR Printer
コンテスト
ユーザー Keroru
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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;
}
0