結果

問題 No.5022 XOR Printer
ユーザー tnktsyk
提出日時 2025-07-26 15:48:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 897 ms / 2,000 ms
コード長 7,374 bytes
コンパイル時間 2,435 ms
コンパイル使用メモリ 217,708 KB
実行使用メモリ 7,716 KB
スコア 4,690,930,565
最終ジャッジ日時 2025-07-26 15:48:51
合計ジャッジ時間 44,334 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

/****************************************************
 * XOR Printer – Multi-scale Block Split (Non-degrading)
 *
 * 1. Start with global best single-s (2^20 exhaustive).
 * 2. Then iterate block sizes sz ∈ {5,4,3,2}.
 *    For each block (tiling the board), do:
 *      - Exhaustively search the best s for ONLY that block.
 *      - Realize diff via XOR-basis built on current board.
 *      - Apply W only inside the block.
 *      - Commit only if global score strictly increases and ops ≤ T.
 * 3. Stop when no block improves or time/ops limit.
 *
 * Hand-tuned for N=10, T=1000.
 ****************************************************/

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>> Ain(N, vector<int>(N));
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin>>Ain[i][j];

    // current board & state
    vector<int> board(NN); for(int i=0;i<N;i++) for(int j=0;j<N;j++) board[i*N+j]=Ain[i][j];
    int curS = 0; // held s
    vector<char> ops; ops.reserve(4000);
    int r=0,c=0; // cursor (0-indexed)

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

    auto time_ok = [&](){ return chrono::duration<double>(chrono::steady_clock::now()-start).count() < TL; };

    // ===== Global best single-s first =====
    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; 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;
        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){
            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;
        }
    }

    // ===== Block sizes loop =====
    vector<int> sizes = {5,4,3,2};
    for(int sz : sizes){
        bool any_improve = true;
        while(any_improve && time_ok() && (int)ops.size() <= T-200){
            any_improve = false;
            for(int rs=0; rs<N; rs+=sz){
                int re = min(N, rs+sz);
                for(int cs=0; cs<N; cs+=sz){
                    int ce = min(N, cs+sz);
                    // collect block ids
                    vector<int> ids; ids.reserve(sz*sz);
                    for(int i=rs;i<re;i++) for(int j=cs;j<ce;j++) ids.push_back(i*N+j);
                    if(ids.empty()) continue;

                    // current block sum
                    ll blkSum=0; for(int id:ids) blkSum+=board[id];

                    // best s on block
                    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;

                    // build basis on whole 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 ^ ts;
                    auto [diffReal, needC] = B.build(diff);
                    int newS = curS ^ diffReal;

                    // recompute real gain on this block
                    vector<int> wCells; wCells.reserve(ids.size());
                    ll newBlk=0;
                    for(int id:ids){ int a=board[id]; int b=a^newS; if(b>a){ wCells.push_back(id); newBlk+=b; } else newBlk+=a; }
                    ll realGain = newBlk - blkSum;
                    if(realGain<=0) continue;

                    // simulate ops
                    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;

                    // commit
                    ops.insert(ops.end(), tmp.begin(), tmp.end());
                    r=tr; c=tc; curS=newS;
                    for(int id:wCells) board[id]^=curS;
                    any_improve = true;
                    if(!time_ok() || (int)ops.size()>T-200) break;
                }
                if(!time_ok() || (int)ops.size()>T-200) break;
            }
        }
    }

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