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

• 問題: No.5022 XOR Printer
• ユーザー: tnktsyk
• 提出日時: 2025-07-26 14:59:36
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 288 ms / 2,000 ms
• コード長: 7,784 bytes
• コンパイル時間: 2,623 ms
• コンパイル使用メモリ: 221,708 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,648,420,920
• 最終ジャッジ日時: 2025-07-26 14:59:55
• 合計ジャッジ時間: 18,489 ms
• ジャッジサーバーID （参考情報）: judge2 / judge6

ファイルパターン	結果
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< vector<int> > idxs[B]; // store list of indices forming the vector (instead of bitset to stay flexible)
    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]==0){ v[b]=x; idxs[b]= {c}; return; }
            x ^= v[b];
            // xor index lists (symmetric difference)
            vector<int> nc; nc.reserve(c.size()+idxs[b][0].size());
            // because both lists are small (<=100) we can brute force
            auto &v1 = c; auto &v2 = idxs[b][0];
            sort(v1.begin(), v1.end());
            sort(v2.begin(), v2.end());
            size_t i=0,j=0;
            while(i<v1.size()||j<v2.size()){
                if(j==v2.size() || (i<v1.size() && v1[i]<v2[j])){ nc.push_back(v1[i]); ++i; }
                else if(i==v1.size() || v2[j]<v1[i]){ nc.push_back(v2[j]); ++j; }
                else{ // equal -> cancel
                    ++i; ++j;
                }
            }
            c.swap(nc);
        }
    }
    // build target -> {built_value, indices}
    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]==0) continue;
            t ^= v[b]; made ^= v[b];
            // xor lists
            vector<int> nc; nc.reserve(sel.size() + idxs[b][0].size());
            auto v1 = sel; auto v2 = idxs[b][0];
            sort(v1.begin(), v1.end());
            sort(v2.begin(), v2.end());
            size_t i=0,j=0;
            while(i<v1.size()||j<v2.size()){
                if(j==v2.size() || (i<v1.size() && v1[i]<v2[j])){ nc.push_back(v1[i]); ++i; }
                else if(i==v1.size() || v2[j]<v1[i]){ nc.push_back(v2[j]); ++j; }
                else{ ++i; ++j; }
            }
            sel.swap(nc);
        }
        return {made, sel};
    }
};

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

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;
    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; 
    vector<int> Aflat(NN); for(int i=0;i<N;i++)for(int j=0;j<N;j++) Aflat[i*N+j]=A2[i][j];

    // Build basis on original board
    XorBasis B1;
    for(int i=0;i<N;i++)for(int j=0;j<N;j++){
        int idx=i*N+j; B1.add(A2[i][j], vector<int>{idx});
    }

    // 1) best single s (exact exhaustive)
    int s1=0; long long best1=-1;
    for(int s=0;s<(1<<20);++s){
        long long sc=score_single(Aflat,s);
        if(sc>best1){best1=sc;s1=s;} }
    auto [s1_real, cset1] = B1.build(s1);
    if(s1_real!=s1){ long long sc=score_single(Aflat,s1_real); if(sc>=best1){best1=sc;s1=s1_real;} }
    if(s1_real!=s1){ auto tmp=B1.build(s1); cset1=tmp.second; }

    // base per cell after stage1 best of {A, A^s1}
    vector<int> baseVal(NN); long long baseSum=0;
    for(int i=0;i<NN;i++){ int a=Aflat[i]; int b=a^s1; baseVal[i]=(b>a?b:a); baseSum+=baseVal[i]; }

    // 2) Find s2 by exhaustive to maximize 4-way value
    int s2=-1; long long gainBest=0;
    for(int s=0;s<(1<<20);++s){
        long long sum=0;
        for(int i=0;i<NN;i++){
            int a=Aflat[i];
            int v0=baseVal[i];
            int v1=a^s; // only stage2
            int v2=(a^s1)^s; // both stages
            int m=v0; if(v1>m)m=v1; if(v2>m)m=v2; sum+=m;
        }
        long long g=sum-baseSum; if(g>gainBest){gainBest=g; s2=s;}
    }

    bool use2 = (gainBest>0);
    vector<unsigned char> choice(NN,0); // 0 none,1 stage1W,2 stage2W,3 both
    if(!use2){
        for(int i=0;i<NN;i++){ int a=Aflat[i]; choice[i]= ((a^s1)>a?1:0); }
    }else{
        // map s2 to achievable after stage1 W changes, so we need to rebuild basis later
        // First decide ideal masks with target s2
        for(int i=0;i<NN;i++){
            int a=Aflat[i]; int v0=a; int v1=a^s1; int v2=a^s2; int v3=a^(s1^s2);
            int best=v0; unsigned char m=0;
            if(v1>best){best=v1;m=1;} if(v2>best){best=v2;m=2;} if(v3>best){best=v3;m=3;}
            choice[i]=m;
        }
    }

    // === Simulate stage1 W to know board for second basis ===
    vector<int> Aafter = Aflat;
    if(use2){
        for(int i=0;i<NN;i++) if(choice[i]&1) Aafter[i]^=s1; // stage1 writes
    }

    // Build basis on modified board to realize delta = s1->s2
    vector<int> csetDelta; int deltaReal=0; int deltaTarget=0;
    if(use2){
        deltaTarget = s1 ^ s2;
        XorBasis B2; for(int i=0;i<N;i++)for(int j=0;j<N;j++){ int idx=i*N+j; B2.add(Aafter[idx], vector<int>{idx}); }
        auto [dReal, csetD] = B2.build(deltaTarget);
        deltaReal=dReal; csetDelta=csetD;
        int s2_real = s1 ^ deltaReal;
        if(s2_real!=s2){
            // recompute gain and masks with s2_real to ensure non-decreasing
            long long sum=0; vector<unsigned char> newChoice(NN);
            for(int i=0;i<NN;i++){
                int a=Aflat[i]; int v0=a; int v1=a^s1; int v2=a^s2_real; int v3=a^(s1^s2_real);
                int best=v0; unsigned char m=0;
                if(v1>best){best=v1;m=1;} if(v2>best){best=v2;m=2;} if(v3>best){best=v3;m=3;}
                newChoice[i]=m; sum+=best;
            }
            if(sum<=baseSum){ use2=false; choice.assign(NN,0); for(int i=0;i<NN;i++){int a=Aflat[i]; choice[i]=((a^s1)>a?1:0);} }
            else{ choice.swap(newChoice); gainBest=sum-baseSum; s2=s2_real; }
        }
    }

    // ===== Build operation sequence =====
    vector<char> ops; int r=0,c=0;
    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);
    }

    auto output_C = [&](const vector<int>& cells){
        // we'll simply visit along snake and C when needed
        vector<char> mark(NN,0); for(int id:cells) mark[id]=1;
        if(!snake.empty()){
            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; int 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);
                }
            }
        }
    };

    // Phase A: make s1
    output_C(cset1);

    // Phase B: stage1 writes (reverse snake)
    if(!snake.empty()){
        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(choice[id]&1) ops.push_back('W');
        }
    }

    if(use2){
        // Phase C: move delta C's
        output_C(csetDelta);
        // Phase D: stage2 writes
        if(!snake.empty()){
            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(choice[id]&2) ops.push_back('W');
            }
        }
    }

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