結果

問題 No.5022 XOR Printer
ユーザー Keroru
提出日時 2025-07-26 15:32:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,281 bytes
コンパイル時間 3,333 ms
コンパイル使用メモリ 292,408 KB
実行使用メモリ 7,720 KB
スコア 0
最終ジャッジ日時 2025-07-26 15:33:06
合計ジャッジ時間 5,188 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Baseline Score: 0
// Improved Score: 1524098986
// Improvement: 1524098986
// XOR Printer greedy solver - snake traversal with local improvements.
// Each cell is visited in snake order. For the current cell x, search within
// distance d (3) for one or two cells a,b that maximise x^s, where s accumulates
// values of selected cells using 'C'. After performing best action we write 'W'
// to apply. Stop when operation count would exceed the limit (1000).

#include <bits/stdc++.h>
using namespace std;

struct Input {
    int N, T;
    vector<vector<long long>> grid;
};

struct Pos {int r, c;};

// Manhattan distance
inline int dist(const Pos& a, const Pos& b){
    return abs(a.r - b.r) + abs(a.c - b.c);
}

// Move from pos a to b, append ops
void append_move(Pos &cur, const Pos &to, string &ops){
    while(cur.r < to.r){ ops += 'D'; cur.r++; }
    while(cur.r > to.r){ ops += 'U'; cur.r--; }
    while(cur.c < to.c){ ops += 'R'; cur.c++; }
    while(cur.c > to.c){ ops += 'L'; cur.c--; }
}

pair<long long,string> solve(const Input& in){
    const int N=in.N; const int T=in.T; const int D=3;
    vector<vector<long long>> G=in.grid;
    string ops; ops.reserve(T);
    Pos cur{0,0}; long long s=0;

    vector<Pos> path; path.reserve(N*N);
    for(int r=0;r<N;r++){
        if(r%2==0){
            for(int c=0;c<N;c++) path.push_back({r,c});
        }else{
            for(int c=N-1;c>=0;c--) path.push_back({r,c});
        }
    }

    auto inside=[&](int r,int c){return 0<=r && r<N && 0<=c && c<N;};

    size_t idx=0;
    while(idx<path.size() && (int)ops.size() < T){
        Pos x = path[idx];
        // move to x if not there
        int moveCost = dist(cur,x);
        if((int)ops.size() + moveCost > T) break;
        append_move(cur,x,ops);

        long long bestVal=G[x.r][x.c];
        int bestType=0; // 0 none,1 one cell,2 two cells
        Pos bestA,bestB; int bestCost=0; long long bestS=s;
        // gather candidate cells within D
        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; // x->a->x plus C,W
            if((int)ops.size()+c1 > T) continue;
            long long ns = s ^ G[a.r][a.c];
            long long val = G[x.r][x.c] ^ 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; // x->a->b->x, C,C,W
            if((int)ops.size()+c2 > T) continue;
            long long ns = s ^ G[a.r][a.c] ^ G[b.r][b.c];
            long long val = G[x.r][x.c] ^ ns;
            if(val>bestVal){
                bestVal=val; bestType=2; bestA=a; bestB=b; bestCost=c2; bestS=ns;
            }
        }
        if(bestType!=0 && (int)ops.size()+bestCost <= T){
            if(bestType==1){
                append_move(cur,bestA,ops); ops+='C';
                append_move(cur,x,ops); ops+='W';
            }else{
                append_move(cur,bestA,ops); ops+='C';
                append_move(cur,bestB,ops); ops+='C';
                append_move(cur,x,ops); ops+='W';
            }
            s=bestS;
            G[x.r][x.c]=bestVal;
        }

        idx++;
        if(idx>=path.size()) break;
        Pos nxt=path[idx];
        int mv = dist(cur,nxt);
        if((int)ops.size()+mv > T) break;
        append_move(cur,nxt,ops);
    }

    long long total=0; for(auto &row:G) for(auto v:row) total+=v;
    // convert operations to whitespace-separated form
    string out;
    out.reserve(2*ops.size());
    for(char c:ops){ out.push_back(c); out.push_back(' '); }
    if(!out.empty()) out.pop_back();
    return {total, out};
}

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