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

• 問題: No.5022 XOR Printer
• ユーザー: tnktsyk
• 提出日時: 2025-07-26 14:16:49
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 5,399 bytes
• コンパイル時間: 2,184 ms
• コンパイル使用メモリ: 209,788 KB
• 実行使用メモリ: 7,716 KB
• スコア: 3,947,485,230
• 最終ジャッジ日時: 2025-07-26 14:16:54
• 合計ジャッジ時間: 4,831 ms
• ジャッジサーバーID （参考情報）: judge6 / 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 repd(i,n) for(auto i=(n)-1;i>=0;i--)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define rep_lt(i,j,n) for(auto i=(j);i<(n);i++)
void printd(ld x){cout<<fixed<<setprecision(16)<<x<<"\n";}
void printd2(ld x,ld y){cout<<fixed<<setprecision(16)<<x<<' '<<y<<"\n";}
template<typename Vec> void vcout(const Vec& v){ for(auto &e:v) cout<<e<<' '; cout<<"\n"; }
template<typename Vec> void vvcout(const Vec& v){ for(auto &r:v){ for(auto &e:r) cout<<e; cout<<"\n"; } }
template<class T,class U> inline void chmax(T& a,const U& b){ if(a<b) a=b; }
template<class T,class U> inline void chmin(T& a,const U& b){ if(a>b) a=b; }
struct FastIO{ FastIO(){ ios::sync_with_stdio(false); cin.tie(nullptr);} } fastio;
void YN(bool s){ cout<<(s?"Yes\n":"No\n"); }
void CY(bool s){ if(s){ cout<<"Yes\n"; exit(0);} }
void CN(bool s){ if(s){ cout<<"No\n"; exit(0);} }
void Cm1(bool s){ if(s){ cout<<-1<<"\n"; exit(0);} }
const ll INF = (ll)4e18;
#define all(p) begin(p), end(p)
#define rall(p) rbegin(p), rend(p)
#define fi first
#define se second
// ===== XOR Basis (20-bit) =====
struct XorBasis {
    static const int B = 20;
    int v[B];                 // basis value
    bitset<128> used[B];      // cells that form this vector
    XorBasis(){ memset(v,0,sizeof(v)); }
    void add(int x, const bitset<128>& bs){
        bitset<128> c = bs;
        for(int b=B-1;b>=0;--b){
            if(((x>>b)&1)==0) continue;
            if(v[b]==0){ v[b]=x; used[b]=c; return; }
            x ^= v[b];
            c ^= used[b];
        }
    }
    // build target -> {built_value, cells_bitset}
    pair<int, bitset<128>> build(int target) const {
        int t = target, made = 0;
        bitset<128> sel; sel.reset();
        for(int b=B-1;b>=0;--b){
            if(((t>>b)&1)==0) continue;
            if(v[b]==0) continue; // cannot set
            t ^= v[b];
            made ^= v[b];
            sel ^= used[b];
        }
        return {made, sel};
    }
};

// Score for a fixed s (no operations counted, purely value)
static inline ll score_with_s(const vector<vector<int>>& A, int s){
    ll sum = 0;
    int n = (int)A.size();
    rep(i,n) rep(j,n){
        int x = A[i][j];
        int y = x ^ s;
        sum += max(x,y);
    }
    return sum;
}

// movement helper
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(){
    int N,T; if(!(cin>>N>>T)) return 0;
    vector<vector<int>> A(N, vector<int>(N));
    rep(i,N) rep(j,N) cin>>A[i][j];

    // ---------- Candidate s0: your sequential greedy ----------
    int s0 = 0;
    rep(i,N) rep(j,N){ if(s0 < (s0 ^ A[i][j])) s0 ^= A[i][j]; }

    // ---------- Candidate s1: per-bit gain max ----------
    int s1_target = 0;
    for(int b=0;b<20;b++){
        int cnt0=0,cnt1=0;
        rep(i,N) rep(j,N){ if((A[i][j]>>b)&1) cnt1++; else cnt0++; }
        if(cnt0 > cnt1) s1_target |= (1<<b);
    }

    // ---------- Build basis ----------
    XorBasis B;
    rep(i,N) rep(j,N){
        bitset<128> bs; bs.reset();
        bs.set(i*N + j);
        B.add(A[i][j], bs);
    }

    auto [s0_real, cells0] = B.build(s0);
    auto [s1_real, cells1] = B.build(s1_target);

    ll sc0 = score_with_s(A, s0_real);
    ll sc1 = score_with_s(A, s1_real);

    // choose better (non-decreasing guarantee vs s0)
    int S = s0_real;            // final s
    bitset<128> needC = cells0; // cells to C
    if(sc1 > sc0){ S = s1_real; needC = cells1; }

    // ---------- Ops construction ----------
    vector<char> ops;
    int r=0,c=0; // current pos (0-index)

    // 1st pass: snake traversal to perform all required C (order doesn't matter)
    vector<pair<int,int>> snake; snake.reserve(N*N);
    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); }
    }
    if(!snake.empty()){
        move_to(r,c,snake[0].fi,snake[0].se,ops);
        for(size_t idx=0; idx<snake.size(); ++idx){
            int rr = snake[idx].fi, cc = snake[idx].se;
            int id = rr*N + cc;
            if(needC.test(id)) ops.push_back('C');
            if(idx+1<snake.size()){
                auto [nr,nc] = snake[idx+1];
                move_to(r,c,nr,nc,ops);
            }
        }
    }

    // 2nd pass: reverse snake to W where beneficial (S is now fixed)
    if(!snake.empty()){
        // currently at snake.back()
        for(size_t idx=0; idx<snake.size(); ++idx){
            auto [rr,cc] = snake[snake.size()-1-idx];
            int id = rr*N + cc;
            // stand there already? if first idx==0, we're on that cell
            if(idx>0){
                move_to(r,c,rr,cc,ops);
            }
            int x = A[rr][cc];
            if( (x ^ S) > x ) ops.push_back('W');
        }
    }

    // Safety: if somehow exceeded, trim (should not happen)
    if((int)ops.size() > T){
        // fallback: output nothing (valid but zero score) -> but better: cut
        // However cutting may break validity. In practice we shouldn't exceed.
        ops.resize(T);
    }

    for(char ch: ops) cout<<ch<<'\n';
    return 0;
}