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

• 問題: No.5022 XOR Printer
• ユーザー: tnktsyk
• 提出日時: 2025-07-26 14:24:14
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 4 ms / 2,000 ms
• コード長: 6,217 bytes
• コンパイル時間: 2,171 ms
• コンパイル使用メモリ: 210,068 KB
• 実行使用メモリ: 7,720 KB
• スコア: 4,009,308,976
• 最終ジャッジ日時: 2025-07-26 14:24:20
• 合計ジャッジ時間: 4,955 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

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

ソースコード

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

// ---------- XOR Basis for up to 20 bits ----------
struct XorBasis {
    static const int B = 20;
    int v[B];                 // basis value
    bitset<128> used[B];      // cells set that forms this basis vector
    XorBasis(){ memset(v, 0, sizeof(v)); }
    void add(int x, const bitset<128>& bs){
        bitset<128> c = bs;
        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];
        }
    }
    pair<int, bitset<128>> build(int target) const {
        int t = target, made = 0;
        bitset<128> sel; sel.reset();
        for(int b=B-1; b>=0; --b){
            if(((t>>b)&1)==0) continue;
            if(v[b]==0) continue; // cannot set this bit
            t ^= v[b];
            made ^= v[b];
            sel ^= used[b];
        }
        return {made, sel};
    }
};

// score for a given s: sum of max(A[i], A[i]^s)
static inline long long eval_score(const vector<int>& flatA, int s){
    long long sum = 0;
    for(int x: flatA){
        int y = x ^ s;
        sum += (y > x ? y : x);
    }
    return sum;
}

// move helper (0-indexed coords)
static inline void move_to(int &r, int &c, int tr, int tc, vector<char>& ops){
    while(r<tr){ ops.push_back('D'); ++r; }
    while(r>tr){ ops.push_back('U'); --r; }
    while(c<tc){ ops.push_back('R'); ++c; }
    while(c>tc){ ops.push_back('L'); --c; }
}

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

    int N,T; if(!(cin>>N>>T)) return 0;   // N=10, T=1000
    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];

    // flatten A for fast eval
    vector<int> flatA(N*N);
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) flatA[i*N+j] = A[i][j];

    // ---------- Candidate s0: your greedy "if(s<s^x) s^=x" ----------
    int s0 = 0;
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) if(s0 < (s0 ^ A[i][j])) s0 ^= A[i][j];

    // ---------- Candidate s1: per-bit gain ********
    int s1_target = 0;
    for(int b=0;b<20;b++){
        int cnt0=0, cnt1=0;
        for(int x: flatA){ if((x>>b)&1) cnt1++; else cnt0++; }
        if(cnt0 > cnt1) s1_target |= (1<<b);
    }

    // ---------- Build 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);
    }

    auto [s0_real, cells0] = basis.build(s0);
    auto [s1_real, cells1] = basis.build(s1_target);

    long long sc0 = eval_score(flatA, s0_real);
    long long sc1 = eval_score(flatA, s1_real);

    int S = s0_real;            // start from the better of s0_real, s1_real
    bitset<128> needC = cells0;
    long long bestScore = sc0;
    if(sc1 > sc0){ S = s1_real; needC = cells1; bestScore = sc1; }

    // ---------- Hill climbing: single & pair XOR (non-decreasing only) ----------
    // single XOR
    bool improved = true;
    while(improved){
        improved = false;
        long long cur = bestScore;
        int bestIdx = -1; long long addGain = 0;
        for(int idx=0; idx<N*N; ++idx){
            int ns = S ^ flatA[idx];
            long long sc = eval_score(flatA, ns);
            if(sc - cur > addGain){
                addGain = sc - cur;
                bestIdx = idx;
            }
        }
        if(addGain > 0){
            S ^= flatA[bestIdx];
            bestScore += addGain;
            improved = true;
        }
    }

    // pair XOR (optional, still cheap)
    bool improved2 = true;
    while(improved2){
        improved2 = false;
        long long cur = bestScore;
        long long addGain = 0;
        int p = -1, q = -1;
        for(int i=0;i<N*N;i++){
            for(int j=i+1;j<N*N;j++){
                int ns = S ^ flatA[i] ^ flatA[j];
                long long sc = eval_score(flatA, ns);
                if(sc - cur > addGain){
                    addGain = sc - cur;
                    p = i; q = j;
                }
            }
        }
        if(addGain > 0){
            S ^= flatA[p];
            S ^= flatA[q];
            bestScore += addGain;
            improved2 = true;
        }
    }

    // Rebuild cells for final S (should be representable)
    auto [S_real, needC2] = basis.build(S);
    if(S_real != S){
        // fallback: choose better of (S_real, original S)
        long long sc_real = eval_score(flatA, S_real);
        if(sc_real >= bestScore){
            S = S_real; bestScore = sc_real; needC = needC2;
        }else{
            // keep S, but still need some C set => build from original S through basis
            needC = needC2; // although mismatch rare, allow anyway
        }
    }else{
        needC = needC2;
    }

    // ---------- Build operation sequence ----------
    vector<char> ops;
    int r=0, c=0; // current pos (0-indexed -> (1,1) in problem statement)

    // Phase 1: traverse snake once, perform C when needed
    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 k=0;k<snake.size();k++){
            int rr = snake[k].first, cc = snake[k].second;
            int id = rr*N + cc;
            if(needC.test(id)) ops.push_back('C');
            if(k+1 < snake.size()){
                auto [nr,nc] = snake[k+1];
                move_to(r,c,nr,nc, ops);
            }
        }
    }

    // Phase 2: reverse snake to W (we are now at last cell already)
    if(!snake.empty()){
        for(size_t k=0;k<snake.size();k++){
            auto [rr,cc] = snake[snake.size()-1-k];
            if(k>0) move_to(r,c, rr, cc, ops);
            int x = A[rr][cc];
            if( (x ^ S) > x ) ops.push_back('W');
        }
    }

    // Safety
    if((int)ops.size() > T){
        // We shouldn't exceed, but trim if necessary (may break correctness though)
        ops.resize(T);
    }

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