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

• 問題: No.5022 XOR Printer
• ユーザー: tnktsyk
• 提出日時: 2025-07-26 15:31:40
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 145 ms / 2,000 ms
• コード長: 7,759 bytes
• コンパイル時間: 2,375 ms
• コンパイル使用メモリ: 217,092 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,282,746,623
• 最終ジャッジ日時: 2025-07-26 15:31:51
• 合計ジャッジ時間: 10,708 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

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

ソースコード

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

/*********************************************************
 * XOR Printer (yukicoder No.5022)
 * Prefix-multi-stage strategy:
 *  - Build an XOR basis on the current board.
 *  - Fix an order of basis vectors (<=20). After k-th COPY block,
 *    s = prefix_xor[0..k]. We allow WRITE at each intermediate s.
 *  - For every cell (except those used in any COPY later), choose the best
 *    stage k (0..m) where A^s_k is maximal. Cells used for COPY are written
 *    only after their last COPY (safe) or skipped.
 *  - Compare the total score with the best single-s baseline (2^20 exhaustive).
 *    If worse, fallback to the baseline solution. Non-degrading.
 *********************************************************/

// ===== XOR Basis over GF(2) for 20-bit ints =====
struct XorBasis {
    static const int B = 20;
    int v[B];                 // basis value
    vector<int> mask[B];      // indices used to form v[b]
    XorBasis(){ memset(v,0,sizeof(v)); }
    void add(int x, const vector<int>& cells){
        vector<int> c = cells;
        for(int b=B-1; b>=0; --b){
            if(((x>>b)&1)==0) continue;
            if(!v[b]){ v[b]=x; mask[b]=c; return; }
            x ^= v[b];
            // symmetric-difference between c and mask[b]
            vector<int> a = mask[b];
            sort(c.begin(), c.end());
            sort(a.begin(), a.end());
            vector<int> res; res.reserve(c.size()+a.size());
            size_t i=0,j=0;
            while(i<c.size()||j<a.size()){
                if(j==a.size() || (i<c.size() && c[i]<a[j])) res.push_back(c[i++]);
                else if(i==c.size() || a[j]<c[i]) res.push_back(a[j++]);
                else { ++i; ++j; }
            }
            c.swap(res);
        }
    }
    // Build target -> {made_value, indices list}
    pair<int, vector<int>> build(int target) const{
        int t=target, made=0; vector<int> sel;
        for(int b=B-1; b>=0; --b){
            if(((t>>b)&1)==0) continue;
            if(!v[b]) continue;
            t ^= v[b]; made ^= v[b];
            vector<int> a = mask[b];
            sort(sel.begin(), sel.end());
            sort(a.begin(), a.end());
            vector<int> res; res.reserve(sel.size()+a.size());
            size_t i=0,j=0;
            while(i<sel.size()||j<a.size()){
                if(j==a.size() || (i<sel.size() && sel[i]<a[j])) res.push_back(sel[i++]);
                else if(i==sel.size() || a[j]<sel[i]) res.push_back(a[j++]);
                else { ++i; ++j; }
            }
            sel.swap(res);
        }
        return {made, sel};
    }
};

inline long long eval_single(const vector<int>& A, int s){
    long long sum=0; for(int x:A){ int y=x^s; sum += (y>x?y:x);} return sum; }

// Greedy visit of given cell list (indices 0..NN-1). Emits opch to ops.
static void visit_cells(int N, int &r, int &c, const vector<int>& ids, vector<char>& ops, char opch){
    if(ids.empty()) return;
    vector<char> used(ids.size(),0);
    for(size_t done=0; done<ids.size(); ++done){
        int best=-1, bestd=1e9;
        for(size_t i=0;i<ids.size();++i){
            if(used[i]) continue;
            int id=ids[i]; int tr=id/N, tc=id%N;
            int d=abs(tr-r)+abs(tc-c);
            if(d<bestd){ bestd=d; best=i; }
        }
        used[best]=1;
        int id=ids[best]; int tr=id/N, tc=id%N;
        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; }
        ops.push_back(opch);
    }
}

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

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

    // Flatten
    vector<int> flatA(NN); for(int i=0;i<N;i++) for(int j=0;j<N;j++) flatA[i*N+j]=A2[i][j];

    // -------- baseline: best single s (2^20 exhaustive) --------
    int bestS_single = 0; long long bestScore_single = -1;
    for(int s=0; s<(1<<20); ++s){
        long long sc = eval_single(flatA, s);
        if(sc > bestScore_single){ bestScore_single=sc; bestS_single=s; }
    }
    // We'll build ops for this baseline if multi-stage fails.

    auto build_single_ops = [&](int S)->vector<char>{
        // Build basis on original board
        XorBasis B;
        for(int i=0;i<N;i++) for(int j=0;j<N;j++){
            int idx=i*N+j; B.add(A2[i][j], vector<int>{idx});
        }
        auto [S_real, cellsC] = B.build(S);
        if(S_real != S){ // try to use realizable one if not worse
            long long sc = eval_single(flatA, S_real);
            if(sc >= bestScore_single){ bestScore_single=sc; S=S_real; }
            else { auto tmp=B.build(S); cellsC = tmp.second; }
        }
        vector<char> ret; ret.reserve(1200);
        int r=0,c=0;
        visit_cells(N,r,c,cellsC,ret,'C');
        // W beneficial cells
        vector<int> wlist;
        for(int id=0; id<NN; ++id){ int a=flatA[id], b=a^S; if(b>a) wlist.push_back(id); }
        visit_cells(N,r,c,wlist,ret,'W');
        if((int)ret.size()>T) ret.resize(T);
        return ret;
    };

    // ---------- Multi-stage prefix plan ----------
    // 1) Build basis on original board and collect independent vectors
    XorBasis B0;
    for(int i=0;i<N;i++) for(int j=0;j<N;j++){
        int idx=i*N+j; B0.add(A2[i][j], vector<int>{idx});
    }
    // Collect non-zero vectors
    struct VecInfo{ int val; vector<int> cells; int msb; };
    vector<VecInfo> vecs;
    for(int b=19;b>=0;b--){ if(B0.v[b]) vecs.push_back({B0.v[b], B0.mask[b], b}); }
    int M = (int)vecs.size();
    // prefix s list s_k (k:0..M) with s_0=0
    vector<int> prefixS(M+1,0);
    for(int k=1;k<=M;k++) prefixS[k] = prefixS[k-1] ^ vecs[k-1].val;

    // union of all C cells
    vector<char> isC(NN,0);
    for(auto &vi:vecs){ for(int id:vi.cells) isC[id]=1; }

    // 2) For each cell decide best stage to write (0..M). If isC, postpone to last stage M only.
    vector<int> bestStage(NN,0); // 0=no write
    vector<int> baseA = flatA;
    for(int id=0; id<NN; ++id){
        int a = baseA[id];
        int bestVal = a; int bestK = 0;
        int startK = isC[id]?M:0; // if C cell, forbid writing before final stage
        for(int k=startK; k<=M; ++k){
            int v = a ^ prefixS[k];
            if(v > bestVal){ bestVal=v; bestK=k; }
        }
        bestStage[id] = bestK;
    }
    // compute total score for plan
    long long score_plan = 0;
    for(int id=0; id<NN; ++id){ score_plan += max(baseA[id], baseA[id]^prefixS[bestStage[id]]); }

    // fallback if worse than single-s
    if(score_plan <= bestScore_single){
        auto ops_single = build_single_ops(bestS_single);
        for(char ch:ops_single) cout<<ch<<'\n';
        return 0;
    }

    // 3) Emit operations stage by stage
    vector<char> ops; ops.reserve(2000);
    int r=0,c=0; int curS = 0;
    for(int k=1;k<=M;k++){
        // COPY for this vector
        // realize vecs[k-1].val increment (since prefix)
        visit_cells(N, r, c, vecs[k-1].cells, ops, 'C');
        curS ^= vecs[k-1].val;
        // WRITE cells assigned to this stage k
        vector<int> wlist; wlist.reserve(NN);
        for(int id=0; id<NN; ++id){ if(bestStage[id]==k) wlist.push_back(id); }
        visit_cells(N, r, c, wlist, ops, 'W');
        // update board values to keep consistency (not strictly needed for score)
    }
    // Stage 0 cells (never written) and others already handled. (If some isC cell best at M but M==0: none).

    if((int)ops.size() > T) ops.resize(T); // safeguard
    for(char ch: ops) cout<<ch<<'\n';
    return 0;
}