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

• 問題: No.5022 XOR Printer
• ユーザー: tnktsyk
• 提出日時: 2025-07-26 15:56:06
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 140 ms / 2,000 ms
• コード長: 6,068 bytes
• コンパイル時間: 2,200 ms
• コンパイル使用メモリ: 217,008 KB
• 実行使用メモリ: 7,720 KB
• スコア: 4,616,838,461
• 最終ジャッジ日時: 2025-07-26 15:56:16
• 合計ジャッジ時間: 9,747 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(auto i=0;i<(n);i++)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define repd(i,n) for(auto i=(n)-1;i>=0;i--)
#define all(p) begin(p),end(p)
#define rall(p) rbegin(p),rend(p)
using P = pair<int,int>;

/**************** 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(all(c)); sort(all(a));
            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);
        }
    }
    // return {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], res; res.reserve(sel.size()+a.size());
            sort(all(sel)); sort(all(a));
            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; }

/************** Greedy visit over id list **************/
static void visit_cells(int N,int &r,int &c,const vector<int>& ids,vector<char>& ops,char op){
    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(op);
    }
}

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 BITS=20, NN=N*N;
    vector<vector<int>> Ain(N,vector<int>(N));
    rep(i,N)rep(j,N) cin>>Ain[i][j];
    vector<int> board(NN); rep(i,N)rep(j,N) board[i*N+j]=Ain[i][j];

    vector<char> ops; ops.reserve(4000);
    int r=0,c=0; // 現在位置
    int curS=0;  // 現在保持している s

    auto start = chrono::steady_clock::now();
    const double TL = 1.90; // 余裕を持った制限
    auto time_ok=[&](){return chrono::duration<double>(chrono::steady_clock::now()-start).count()<TL;};

    // ---- Step0: 全体で最良の単一 s を 2^20 全探索 ----
    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){
        XorBasis B; rep(i,N)rep(j,N){ int id=i*N+j; B.add(board[id], {id}); }
        int diff = curS ^ bestS;
        auto [diffReal, needC] = B.build(diff);
        int newS = curS ^ diffReal;
        vector<int> wCells; wCells.reserve(NN); ll afterSum=0;
        rep(id,NN){ int a=board[id]; int b=a^newS; if(b>a){ wCells.push_back(id); afterSum+=b;} else afterSum+=a; }
        if(afterSum>baseSum){
            visit_cells(N,r,c,needC,ops,'C'); curS=newS;
            visit_cells(N,r,c,wCells,ops,'W'); for(int id:wCells) board[id]^=curS;
        }
    }

    // ---- Step1: ビット単位ヒルクライム ----
    while(time_ok() && (int)ops.size() <= T-200){
        // 各ビットの利得を計算し、最大利得ビットを 1 つ適用
        ll curSum=0; for(int v:board) curSum+=v;
        int bestBit=-1; ll gainBest=0; int bestNewS=curS; vector<int> bestNeedC, bestW;

        // 基底は 1 回だけ作って再利用
        XorBasis B; rep(i,N)rep(j,N){ int id=i*N+j; B.add(board[id], {id}); }

        for(int b=BITS-1;b>=0;b--){
            int targetS = curS ^ (1<<b); // toggle bit b
            int diff = curS ^ targetS;   // = 1<<b
            auto [diffReal, needC] = B.build(diff);
            int newS = curS ^ diffReal;
            // 計算した newS での利得
            ll gain=0; vector<int> wCells; wCells.reserve(NN);
            rep(id,NN){ int a=board[id]; int bval=a^newS; if(bval>a){ gain+= (bval-a); wCells.push_back(id);} }
            if(gain>gainBest){ gainBest=gain; bestBit=b; bestNewS=newS; bestNeedC=needC; bestW=wCells; }
        }
        if(gainBest<=0) break; // もう改善なし

        // ops 予測・チェック
        vector<char> tmp; tmp.reserve(bestNeedC.size()*6 + bestW.size()*6 + 10);
        int tr=r, tc=c;
        visit_cells(N,tr,tc,bestNeedC,tmp,'C');
        visit_cells(N,tr,tc,bestW,tmp,'W');
        if((int)ops.size() + (int)tmp.size() > T) break; // 余裕なし

        // 適用
        ops.insert(ops.end(), all(tmp));
        r=tr; c=tc; curS=bestNewS;
        for(int id:bestW) board[id]^=curS;
    }

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