結果

問題 No.5022 XOR Printer
コンテスト
ユーザー tnktsyk
提出日時 2025-07-26 15:15:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 551 ms / 2,000 ms
コード長 4,965 bytes
コンパイル時間 2,370 ms
コンパイル使用メモリ 212,088 KB
実行使用メモリ 7,716 KB
スコア 4,648,420,920
最終ジャッジ日時 2025-07-26 15:16:22
合計ジャッジ時間 31,693 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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];
    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 diff of sorted vectors
            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_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 route over specified ids (0..NN-1). start at (r,c) and mutate them. emit opch for each cell visited in order.
static void visit_cells(int N, int &r, int &c, const vector<int>& ids, vector<char>& ops, char opch){
    vector<char> used(ids.size(),0);
    int cur_r=r, cur_c=c;
    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-cur_r)+abs(cc-cur_c); if(d<bestd){bestd=d; best=i;} }
        used[best]=1; int id=ids[best]; int rr=id/N, cc=id%N;
        while(cur_r<rr){ ops.push_back('D'); ++cur_r; }
        while(cur_r>rr){ ops.push_back('U'); --cur_r; }
        while(cur_c<cc){ ops.push_back('R'); ++cur_c; }
        while(cur_c>cc){ ops.push_back('L'); --cur_c; }
        ops.push_back(opch);
    }
    r=cur_r; c=cur_c;
}

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;
    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];

    vector<int> board(NN); for(int i=0;i<N;i++)for(int j=0;j<N;j++) board[i*N+j]=A2[i][j];

    vector<char> ops; ops.reserve(2000);
    int r=0,c=0; // current pos (0-indexed)
    int curS = 0;

    auto start = chrono::steady_clock::now();
    const double TL = 1.85; // seconds safe margin

    while(true){
        if((int)ops.size() > T-200) break; // spare
        double t = chrono::duration<double>(chrono::steady_clock::now()-start).count();
        if(t>TL) break;

        // base sum
        ll baseSum=0; for(int v:board) baseSum+=v;

        // exhaustive best s on current board
        int targetS=-1; ll bestGain=0;
        for(int s=0;s<(1<<20);++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; targetS=s;} }
        if(bestGain<=0) break;

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

        // decide which cells to W
        vector<int> wlist; wlist.reserve(NN);
        ll afterSum=0;
        for(int id=0; id<NN; ++id){
            int a=board[id], b=a^newS; if(b>a){ wlist.push_back(id); afterSum+=b; } else afterSum+=a; }
        if(afterSum <= baseSum) break;

        // simulate op count to check T
        size_t need_ops = ops.size();
        // rough path cost: greedy path length <= manhattan bound: (#C + #W)*5 avg
        // We'll just trust T check after emitting; if exceed, break before printing final

        // emit C
        if(!needC.empty()) visit_cells(N, r, c, needC, ops, 'C');
        curS = newS;
        // emit W
        if(!wlist.empty()) visit_cells(N, r, c, wlist, ops, 'W');
        // update board
        for(int id: wlist) board[id] ^= curS;
    }

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