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

• 問題: No.5022 XOR Printer
• ユーザー: tnktsyk
• 提出日時: 2025-07-26 13:42:35
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 6,782 bytes
• コンパイル時間: 2,804 ms
• コンパイル使用メモリ: 221,616 KB
• 実行使用メモリ: 7,716 KB
• スコア: 2,704,524,036
• 最終ジャッジ日時: 2025-07-26 13:42:41
• 合計ジャッジ時間: 5,277 ms
• ジャッジサーバーID （参考情報）: judge2 / judge6

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

ソースコード

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

// ===== XOR Basis over GF(2) for 20-bit ints =====
struct XorBasis {
    static const int B = 20; // bits 0..19
    int v[B];                 // basis vectors (value)
    bitset<128> used[B];      // which cells compose this vector
    XorBasis(){ memset(v, 0, sizeof(v)); }
    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];
        }
    }
    // return (built_value, cells_bitset)
    pair<int, bitset<128>> build(int target) const {
        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: append ops to go from (r1,c1) -> (r2,c2)
static inline 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;
    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. Count per-bit gains =====
    const int B = 20;
    vector<int> cnt0(B,0), cnt1(B,0);
    for(int i=0;i<N;i++) for(int j=0;j<N;j++){
        int x = A[i][j];
        for(int b=0;b<B;b++){
            if((x>>b)&1) cnt1[b]++; else cnt0[b]++;
        }
    }
    vector<ll> gain(B);
    for(int b=0;b<B;b++) gain[b] = 1LL*(cnt0[b] - cnt1[b])*(1LL<<b);

    // ===== 2. Decide s2_target (full best) =====
    int s2_target = 0;
    for(int b=0;b<B;b++) if(gain[b] > 0) s2_target |= (1<<b);

    // ===== 3. Decide s1_target (upper bits only) =====
    //   Strategy: take positive-gain bits with b>=15 first. If none, take top few positive bits by gain.
    int s1_target = 0;
    const int TH = 15; // upper-bit threshold (0-indexed)
    for(int b=TH;b<B;b++) if(gain[b] > 0) s1_target |= (1<<b);
    if(s1_target == 0){
        // fallback: pick up to 6 best positive bits by gain
        vector<pair<ll,int>> cand;
        for(int b=0;b<B;b++) if(gain[b]>0) cand.push_back({gain[b], b});
        sort(cand.rbegin(), cand.rend());
        for(int i=0;i<(int)cand.size() && i<6;i++) s1_target |= (1<<cand[i].second);
    }

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

    // Build s1 and s2 from basis
    auto [s1_real, cells1] = basis.build(s1_target);
    auto [s2_real, cells2] = basis.build(s2_target);

    // diff cells needed to go from s1 -> s2
    bitset<128> diff = cells1 ^ cells2;

    // ===== 5. Precompute best choice per cell =====
    // choices: 0=none, 1=W at stage1 only, 2=W at stage2 only, 3=both
    vector<int> choice(N*N, 0);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int idx = i*N + j;
            int a = A[i][j];
            int v0 = a;
            int v1 = a ^ s1_real;
            int v2 = a ^ s2_real;
            int v3 = a ^ s1_real ^ s2_real;
            int bestv = v0; int bestc = 0;
            if(v1 > bestv){ bestv=v1; bestc=1; }
            if(v2 > bestv){ bestv=v2; bestc=2; }
            if(v3 > bestv){ bestv=v3; bestc=3; }
            choice[idx] = bestc;
        }
    }

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

    // ===== 6. Phase C1: build s1 =====
    vector<int> targets1;
    for(int idx=0; idx<N*N; ++idx) if(cells1.test(idx)) targets1.push_back(idx);
    // nearest neighbor greedy
    vector<int> used1(targets1.size(), 0);
    for(size_t done=0; done<targets1.size(); ++done){
        int best=-1, bestd=1e9;
        for(size_t k=0;k<targets1.size();++k){
            if(used1[k]) continue;
            int rr = targets1[k]/N, cc = targets1[k]%N;
            int d = abs(rr-r)+abs(cc-c);
            if(d < bestd){ bestd=d; best=(int)k; }
        }
        used1[best]=1;
        int tr = targets1[best]/N, tc = targets1[best]%N;
        move_to(r,c,tr,tc,ops);
        ops.push_back('C');
    }

    // ===== 7. Stage1 snake + W1 =====
    vector<pair<int,int>> snake;
    snake.reserve(N*N);
    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); }
    }
    if(!snake.empty()){
        move_to(r,c,snake[0].first, snake[0].second, ops);
        for(size_t idx=0; idx<snake.size(); ++idx){
            int rr = snake[idx].first, cc = snake[idx].second;
            int id = rr*N + cc;
            if(choice[id] == 1 || choice[id] == 3) ops.push_back('W');
            if(idx+1 < snake.size()){
                auto [nr,nc] = snake[idx+1];
                move_to(r,c,nr,nc,ops);
            }
        }
    }

    // ===== 8. Phase C2 diff: build s2 from s1 =====
    vector<int> targets2;
    for(int idx=0; idx<N*N; ++idx) if(diff.test(idx)) targets2.push_back(idx);
    vector<int> used2(targets2.size(), 0);
    for(size_t done=0; done<targets2.size(); ++done){
        int best=-1, bestd=1e9;
        for(size_t k=0;k<targets2.size();++k){
            if(used2[k]) continue;
            int rr = targets2[k]/N, cc = targets2[k]%N;
            int d = abs(rr-r)+abs(cc-c);
            if(d < bestd){ bestd=d; best=(int)k; }
        }
        used2[best]=1;
        int tr = targets2[best]/N, tc = targets2[best]%N;
        move_to(r,c,tr,tc,ops);
        ops.push_back('C');
    }

    // ===== 9. Stage2 snake + W2 =====
    if(!snake.empty()){
        move_to(r,c,snake[0].first, snake[0].second, ops);
        for(size_t idx=0; idx<snake.size(); ++idx){
            int rr = snake[idx].first, cc = snake[idx].second;
            int id = rr*N + cc;
            if(choice[id] == 2 || choice[id] == 3) ops.push_back('W');
            if(idx+1 < snake.size()){
                auto [nr,nc] = snake[idx+1];
                move_to(r,c,nr,nc,ops);
            }
        }
    }

    // ===== 10. Truncate if needed (safety) =====
    if((int)ops.size() > T){
        // Simple fallback: cut to T (may invalidate path, but keeps WA away)
        ops.resize(T);
    }

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