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

• 問題: No.5022 XOR Printer
• ユーザー: tnktsyk
• 提出日時: 2025-07-26 15:42:59
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 486 ms / 2,000 ms
• コード長: 7,560 bytes
• コンパイル時間: 2,620 ms
• コンパイル使用メモリ: 219,976 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,690,930,565
• 最終ジャッジ日時: 2025-07-26 15:43:25
• 合計ジャッジ時間: 23,329 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

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

ソースコード

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

/****************************************************
 *  XOR Printer – Block Split Non-degrading Version
 *  - Start with best single-s (2^20 exhaustive) to get a strong base.
 *  - Then repeat over 5x5 quadrants (4 blocks): for each block, search
 *    the best s (2^20) that improves ONLY that block (rest unchanged).
 *    Apply it (C diff + W in that block) iff global score strictly increases.
 *  - Greedy routing only over required cells (C/W) to save ops so we can
 *    process multiple blocks within T=1000.
 *  - Every adoption is guarded by score comparison ⇒ non-degrading.
 ****************************************************/

// ===== XOR Basis (20-bit) =====
struct XorBasis {
    static const int B = 20;
    int v[B];
    vector<int> mask[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];
            vector<int> a = mask[b], res; res.reserve(c.size()+a.size());
            sort(c.begin(),c.end()); sort(a.begin(),a.end());
            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);
        }
    }
    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], res; res.reserve(sel.size()+a.size());
            sort(sel.begin(),sel.end()); sort(a.begin(),a.end());
            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 ll eval_single(const vector<int>& A, int s){
    ll sum=0; for(int x:A){ int y=x^s; sum += (y>x?y:x);} return sum; }

static void greedy_visit(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 rr=id/N, cc=id%N; int d=abs(rr-r)+abs(cc-c); if(d<bestd){bestd=d; best=(int)i;} }
        used[best]=1; int id=ids[best]; int rr=id/N, cc=id%N;
        while(r<rr){ ops.push_back('D'); ++r; }
        while(r>rr){ ops.push_back('U'); --r; }
        while(c<cc){ ops.push_back('R'); ++c; }
        while(c>cc){ 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, BITS=20;
    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 board
    vector<int> board(NN); for(int i=0;i<N;i++) for(int j=0;j<N;j++) board[i*N+j]=A[i][j];

    vector<char> ops; ops.reserve(3000);
    int r=0,c=0;      // cursor
    int curS = 0;     // current s held

    auto start = chrono::steady_clock::now();
    const double TIME_LIMIT = 1.90; // seconds safety

    // ====== STEP 1: global best single s ======
    ll baseSum = 0; for(int v:board) baseSum+=v;
    int bestS = 0; ll bestGain = 0;
    for(int s=0; s<(1<<BITS); ++s){
        ll tot=0; for(int x:board){ int y=x^s; tot += (y>x?y:x);} ll g=tot-baseSum; if(g>bestGain){bestGain=g; bestS=s;}
    }
    if(bestGain>0){
        // Build basis from board
        XorBasis B; for(int i=0;i<N;i++)for(int j=0;j<N;j++){ int idx=i*N+j; B.add(board[idx], vector<int>{idx}); }
        int diff = curS ^ bestS;
        auto [diffReal, needC] = B.build(diff);
        int newS = curS ^ diffReal;
        // recompute with realizable s
        vector<int> wCells; wCells.reserve(NN);
        ll afterSum=0;
        for(int id=0; id<NN; ++id){
            int a=board[id]; int b=a^newS;
            if(b>a){ wCells.push_back(id); afterSum+=b; } else afterSum+=a;
        }
        if(afterSum>baseSum){
            // emit
            greedy_visit(N,r,c,needC,ops,'C'); curS=newS;
            greedy_visit(N,r,c,wCells,ops,'W');
            for(int id:wCells) board[id]^=curS;
        }
    }

    // ====== STEP 2: block loop ======
    // Quadrants: 5x5 each
    vector<pair<int,int>> ranges = {{0,5},{5,10}}; // [l,r)
    auto elapsed = [&](){return chrono::duration<double>(chrono::steady_clock::now()-start).count();};

    bool improved=true;
    while(improved){
        improved=false;
        if((int)ops.size()>T-200) break;
        if(elapsed()>TIME_LIMIT) break;

        // try each block
        for(auto [ri,re]:ranges){
            for(auto [ci,ce]:ranges){
                // collect ids of this block
                vector<int> ids; ids.reserve(25);
                for(int i=ri;i<re;i++) for(int j=ci;j<ce;j++) ids.push_back(i*N+j);
                // compute current block sum
                ll blkSum=0; for(int id:ids) blkSum+=board[id];
                // exhaustive best s on this block (considering only these cells)
                int ts=-1; ll gain=0;
                for(int s=0;s<(1<<BITS);++s){
                    ll tot=0; for(int id:ids){ int a=board[id]; int b=a^s; tot += (b>a?b:a);} ll g=tot-blkSum; if(g>gain){gain=g; ts=s;}
                }
                if(gain<=0) continue; // block cannot improve by itself
                // realize diff with current board
                int diff = curS ^ ts;
                XorBasis B; for(int i=0;i<N;i++) for(int j=0;j<N;j++){ int idx=i*N+j; B.add(board[idx], vector<int>{idx}); }
                auto [diffReal, needC] = B.build(diff);
                int newS = curS ^ diffReal;
                // re-eval gain on block with realizable newS
                vector<int> wCells; wCells.reserve(ids.size());
                ll newBlkSum=0;
                for(int id:ids){ int a=board[id]; int b=a^newS; if(b>a){ wCells.push_back(id); newBlkSum+=b;} else newBlkSum+=a; }
                ll realGain = newBlkSum - blkSum;
                if(realGain<=0) continue; // skip
                // also check total ops budget
                vector<char> tmp; tmp.reserve(needC.size()*6 + wCells.size()*6 + 10);
                int tr=r, tc=c;
                greedy_visit(N,tr,tc,needC,tmp,'C');
                greedy_visit(N,tr,tc,wCells,tmp,'W');
                if((int)ops.size()+ (int)tmp.size() > T) continue; // can't afford
                // commit
                ops.insert(ops.end(), tmp.begin(), tmp.end());
                r=tr; c=tc; curS=newS;
                for(int id:wCells) board[id]^=curS;
                improved=true;
                if((int)ops.size()>T-200) break;
                if(elapsed()>TIME_LIMIT) break;
            }
            if(improved && (int)ops.size()>T-200) break;
            if(elapsed()>TIME_LIMIT) break;
        }
    }

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