結果

問題 No.5022 XOR Printer
ユーザー tnktsyk
提出日時 2025-07-26 14:39:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 142 ms / 2,000 ms
コード長 4,385 bytes
コンパイル時間 1,967 ms
コンパイル使用メモリ 209,860 KB
実行使用メモリ 7,720 KB
スコア 4,009,322,229
最終ジャッジ日時 2025-07-26 14:39:44
合計ジャッジ時間 10,052 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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];
    bitset<128> used[B];
    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];
        }
    }
    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 that bit
            t ^= v[b]; made ^= v[b]; sel ^= used[b];
        }
        return {made, sel};
    }
};

static inline long long eval_score(const vector<int>& A, int s){
    long long 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];

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

    // --- baseline s candidates ---
    int s0 = 0; // greedy
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) if(s0 < (s0 ^ A2[i][j])) s0 ^= A2[i][j];

    int s1_target = 0; // per-bit gain
    for(int b=0;b<20;b++){
        int cnt0=0,cnt1=0;
        for(int x: flatA){ if((x>>b)&1) cnt1++; else cnt0++; }
        if(cnt0 > cnt1) s1_target |= (1<<b);
    }

    // build basis
    XorBasis basis;
    for(int i=0;i<N;i++) for(int j=0;j<N;j++){
        bitset<128> bs; bs.reset(); bs.set(i*N + j);
        basis.add(A2[i][j], bs);
    }

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

    int bestS = s0_real; bitset<128> bestC = cells0; long long bestScore = eval_score(flatA, bestS);
    {
        long long sc1 = eval_score(flatA, s1_real);
        if(sc1 > bestScore){ bestScore=sc1; bestS=s1_real; bestC=cells1; }
    }

    // --- exhaustive search over all 2^20 s ---
    // keep non-decreasing guarantee: only replace when strictly better
    const int LIMIT = 1<<20; // 1,048,576
    for(int s=0; s<LIMIT; ++s){
        long long sc = eval_score(flatA, s);
        if(sc > bestScore){
            bestScore = sc;
            bestS = s;
        }
    }

    // map bestS to achievable S_real via basis
    auto [S_real, cells_final] = basis.build(bestS);
    if(S_real != bestS){
        long long sc_real = eval_score(flatA, S_real);
        if(sc_real >= bestScore){ bestScore=sc_real; bestS=S_real; bestC=cells_final; }
        // else keep previous bestS; but we still need some C set. Build again from that bestS just in case
        else { bestC = cells_final; }
    }else{
        bestC = cells_final;
    }

    // ---- construct ops ----
    vector<char> ops;
    int r=0,c=0;
    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].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(bestC.test(id)) ops.push_back('C');
            if(k+1<snake.size()){
                auto [nr,nc] = snake[k+1];
                move_to(r,c,nr,nc,ops);
            }
        }
    }

    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 x = A2[rr][cc];
            if( (x ^ bestS) > x ) ops.push_back('W');
        }
    }

    if((int)ops.size() > T) ops.resize(T); // unlikely

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