#1107805 (C++17) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: tnktsyk
• 提出日時: 2025-07-26 13:22:42
• 言語: C++17 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 4,432 bytes
• コンパイル時間: 2,181 ms
• コンパイル使用メモリ: 209,176 KB
• 実行使用メモリ: 7,716 KB
• スコア: 3,406,653,505
• 最終ジャッジ日時: 2025-07-26 13:22:47
• 合計ジャッジ時間: 4,440 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
other	AC * 50

ソースコード

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

// ===== XOR Basis over GF(2) for 20-bit ints =====
struct XorBasis {
    static const int B = 20; // 0..19 bits
    int v[B];                 // basis vector values
    bitset<128> used[B];      // which cells compose this basis vector
    XorBasis(){ memset(v, 0, sizeof(v)); }
    // add vector x with its cell-bitset "cells" into basis
    void add(int x, const bitset<128>& cells){
        bitset<128> c = cells;
        for(int b=B-1; b>=0; --b){
            if(((x>>b)&1)==0) continue;
            if(v[b]==0){
                v[b] = x;
                used[b] = c;
                return;
            }
            x ^= v[b];
            c ^= used[b];
        }
    }
    // try to build target. returns {achieved_value, cells_to_xor}
    pair<int, bitset<128>> build(int target){
        int t = target;
        int built = 0;
        bitset<128> ans; ans.reset();
        for(int b=B-1; b>=0; --b){
            if(((t>>b)&1)==0) continue;
            if(v[b]==0) continue; // can't set this bit
            t ^= v[b];
            built ^= v[b];
            ans ^= used[b];
        }
        return {built, ans};
    }
};

// Move helper: push operations to go from (r1,c1) to (r2,c2)
void move_to(int &r1, int &c1, int r2, int c2, vector<char>& ops){
    while(r1 < r2){ ops.push_back('D'); ++r1; }
    while(r1 > r2){ ops.push_back('U'); --r1; }
    while(c1 < c2){ ops.push_back('R'); ++c1; }
    while(c1 > c2){ ops.push_back('L'); --c1; }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N, T; if(!(cin>>N>>T)) return 0; // N=10, T=1000 expected
    vector<vector<int>> A(N, vector<int>(N));
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin>>A[i][j];

    // 1) decide s_target by per-bit gain
    int s_target = 0;
    for(int b=0;b<20;b++){
        int cnt0=0, cnt1=0;
        for(int i=0;i<N;i++) for(int j=0;j<N;j++){
            if((A[i][j]>>b)&1) cnt1++; else cnt0++;
        }
        if(cnt0 > cnt1) s_target |= (1<<b);
    }

    // 2) build XOR basis
    XorBasis B;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int idx = i*N + j;
            bitset<128> bs; bs.reset(); bs.set(idx);
            B.add(A[i][j], bs);
        }
    }

    auto [s_built, need_cells] = B.build(s_target);
    // s we can actually realize
    int S_VAL = s_built;

    // Collect indices to XOR (C) to form s
    vector<int> targets;
    for(int idx=0; idx<N*N; ++idx){ if(need_cells.test(idx)) targets.push_back(idx); }

    // Simple greedy visiting order (nearest neighbor)
    vector<int> order;
    int cur_r = 0, cur_c = 0;
    vector<int> used_flag(targets.size(), 0);
    for(size_t done=0; done<targets.size(); ++done){
        int best = -1; int bestd = 1e9;
        for(size_t k=0;k<targets.size();++k){
            if(used_flag[k]) continue;
            int r = targets[k]/N, c = targets[k]%N;
            int d = abs(r-cur_r)+abs(c-cur_c);
            if(d < bestd){ bestd=d; best=(int)k; }
        }
        used_flag[best]=1;
        order.push_back(targets[best]);
        cur_r = targets[best]/N;
        cur_c = targets[best]%N;
    }

    vector<char> ops;
    int r=0,c=0; // start position (1,1) -> (0,0)

    // Phase 1: visit C cells to build s
    for(int idx : order){
        int tr = idx / N, tc = idx % N;
        move_to(r,c,tr,tc,ops);
        ops.push_back('C');
    }

    // Phase 2: snake traversal and W where beneficial
    // Build snake path
    vector<pair<int,int>> snake;
    for(int i=0;i<N;i++){
        if(i%2==0){
            for(int j=0;j<N;j++) snake.emplace_back(i,j);
        }else{
            for(int j=N-1;j>=0;j--) snake.emplace_back(i,j);
        }
    }
    // Move to start of snake
    if(!snake.empty()){
        move_to(r,c,snake[0].first, snake[0].second, ops);
        for(size_t k=0;k<snake.size();++k){
            auto [rr,cc] = snake[k];
            // At cell
            ll gain = ((A[rr][cc] ^ S_VAL) - A[rr][cc]);
            if(gain > 0) ops.push_back('W');
            // Move to next cell
            if(k+1<snake.size()){
                auto [nr,nc] = snake[k+1];
                move_to(r,c,nr,nc,ops);
            }
        }
    }

    // Safety: truncate if ops exceed T (shouldn't happen in practice)
    if((int)ops.size() > T){
        ops.resize(T);
    }

    // Output
    for(char ch: ops) cout << ch << '\n';
    return 0;
}