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

• 問題: No.5022 XOR Printer
• ユーザー: tnktsyk
• 提出日時: 2025-07-26 15:08:59
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 321 ms / 2,000 ms
• コード長: 5,318 bytes
• コンパイル時間: 2,311 ms
• コンパイル使用メモリ: 217,180 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,648,420,920
• 最終ジャッジ日時: 2025-07-26 15:09:21
• 合計ジャッジ時間: 19,228 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

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

ソースコード

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

// ===== 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];
            // symmetric difference of two sorted vectors
            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_score(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 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>> A2(N, vector<int>(N));
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin>>A2[i][j];
    const int NN=N*N;

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

    // snake path
    vector<pair<int,int>> snake; snake.reserve(NN);
    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);
    }

    vector<char> ops; ops.reserve(2000);
    int r=0,c=0; // current pos
    auto do_C = [&](const vector<int>& need){
        vector<char> mark(NN,0); for(int id:need) mark[id]=1;
        if(snake.empty()) return;
        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, id=rr*N+cc;
            if(mark[id]) ops.push_back('C');
            if(k+1<snake.size()){
                auto [nr,nc]=snake[k+1]; move_to(r,c,nr,nc,ops);
            }
        }
    };
    auto do_W = [&](const vector<char>& take, int s){
        if(snake.empty()) return;
        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 id=rr*N+cc; if(take[id]){ ops.push_back('W'); board[id]^=s; }
        }
    };

    // current s held by the cursor
    int curS = 0;

    // time/ops guard
    auto start = chrono::steady_clock::now();
    const double TL = 1.85; // seconds

    while(true){
        // stop if we cannot afford another full pass
        if((int)ops.size() + 2*NN + 200 >= T) break;
        double t = chrono::duration<double>(chrono::steady_clock::now()-start).count();
        if(t > TL) break;

        // base sum
        ll baseSum=0; for(int v:board) baseSum+=v;

        // ---- choose best s for current board (full search) ----
        int targetS=-1; ll bestGain=0; // gain over baseSum
        for(int s=0;s<(1<<20);++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; targetS=s; }
        }
        if(bestGain<=0) break; // no improvement left

        // ---- realize diff on current board ----
        int diff = curS ^ targetS;
        // build basis from current board values (before W)
        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;

        // recompute take mask with realizable newS and check gain
        vector<char> take(NN,0);
        ll afterSum=0;
        for(int id=0; id<NN; ++id){
            int a=board[id]; int b=a^newS;
            if(b>a){ take[id]=1; afterSum+=b; } else afterSum+=a;
        }
        if(afterSum <= baseSum) break; // no actual gain

        // emit ops
        do_C(needC);
        curS = newS;
        do_W(take, curS);
    }

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