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

• 問題: No.5022 XOR Printer
• ユーザー: twins_fuyu
• 提出日時: 2026-02-03 06:54:22
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 21 ms / 2,000 ms
• コード長: 9,990 bytes
• コンパイル時間: 5,900 ms
• コンパイル使用メモリ: 380,660 KB
• 実行使用メモリ: 7,848 KB
• スコア: 5,079,663,578
• 最終ジャッジ日時: 2026-02-03 06:54:38
• 合計ジャッジ時間: 9,729 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
other	AC * 50

ソースコード

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "immintrin.h"
using namespace std;
#define rep1(a) for (int _ = 0; _ < (a); ++_)
#define rep2(i, a) for (int i = 0; i < (a); ++i)
#define rep3(i, a, b) for (int i = a; i < (b); ++i)
#define rrep1(a) for (int i = (a) - 1; i >= 0; --i)
#define rrep2(i, a) for (int i = (a) - 1; i >= 0; --i)
#define rrep3(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) overload3(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define in(i, vec) for (auto i : (vec))
template <class T>
using pqueue = priority_queue<T, vector<T>>; // 大きい順
template <class T>
using pqueue_g = priority_queue<T, vector<T>, greater<T>>; // 小さい順

namespace library
{
    class xorshift128plus
    {
    private:
        uint64_t s[2];

    public:
        using result_type = uint64_t;

        xorshift128plus(uint64_t seed = 1)
        {
            seed_gen(seed);
        }

        void seed(uint64_t seed_val)
        {
            seed_gen(seed_val);
        }

        static constexpr result_type min()
        {
            return std::numeric_limits<result_type>::min();
        }

        static constexpr result_type max()
        {
            return std::numeric_limits<result_type>::max();
        }

        result_type operator()()
        {
            uint64_t s1 = s[0];
            uint64_t s0 = s[1];
            s[0] = s0;
            s1 ^= s1 << 23;
            s[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26);
            return s[1] + s0;
        }

    private:
        void seed_gen(uint64_t seed_val)
        {
            // SplitMix64 で状態2個を初期化
            s[0] = splitmix64(seed_val);
            s[1] = splitmix64(s[0]);
        }

        static uint64_t splitmix64(uint64_t &x)
        {
            x += 0x9E3779B97F4A7C15ULL;
            uint64_t z = x;
            z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
            z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
            return z ^ (z >> 31);
        }
    };

    struct Timer
    {
        chrono::steady_clock::time_point start;
        Timer() : start(chrono::steady_clock::now()) {}
        double elapse()
        {
            return chrono::duration<double>(chrono::steady_clock::now() - start).count();
        }
        bool over(double t)
        {
            return elapse() > t;
        }
        bool operator()(double t)
        {
            return elapse() < t;
        }
    };

    void fast_io()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }

    uint64_t exp_table[2001];

    bool init_exp_table(){
        for(int i=0;i<=2000;++i){
            exp_table[i]=numeric_limits<uint64_t>::max()*exp(double(-i)/100.0);
        }
        return true;
    }
    bool exp_table_initialized = init_exp_table();

    uint64_t sa_exp(double diff, double temperature){
        if(temperature==0) return 0;
        else if (diff>=0) return numeric_limits<uint64_t>::max();
        int index = int(-diff * 100.0 / temperature);
        if(index>2000) return 0;
        return exp_table[index];
    }

} // namespace library

uniform_real_distribution<double> rnd(0.0, 1.0);
normal_distribution<double> randn(0.0, 1.0);
library::xorshift128plus rng(12345);
library::Timer timer;
double TL = 1.9;

constexpr int N = 10;
constexpr int NN = N * N;
constexpr int T = 1000;

uint32_t A[N][N];
vector<pair<int,int>> order;


/*
...0123...
...7654...
...89AB...
*/

struct Input{
    void get(){
        int n,t; cin>>n>>t;
        assert(n==N && t==T);
        rep(i,N)rep(j,N) cin>>A[i][j];
        rep(i,N)rep(j,N) order.emplace_back(i,j);
    }
};
Input input;

int clz20(uint32_t bit){
    return bit==0?20:__builtin_clz(bit)-12;
}

int cx = 0, cy = 0;
uint32_t s = 0;

string Out;

vector<tuple<int,int,int>> targets = {
    {0,0,0},{1,0,1},{2,0,2},{3,0,3},
    {4,1,3},{5,1,2},{6,1,1},{7,1,0},
};

int O[N][N] = {};
pair<int,int> iO[NN] = {};

void init_O(){
    int cx=0,cy=0;
    int o=0;
    rep(i,10){
        O[cx][cy]=o++;
        if(i!=9) cy++;
        else cx++;
    }
    rep(i,2){
        rep(j,4){
            O[cx][cy]=o++;
            cy--;
            O[cx][cy]=o++;
            cx++;
            O[cx][cy]=o++;
            cy++;
            O[cx][cy]=o++;
            cx++;
        }
        O[cx][cy]=o++; cy--;
        O[cx][cy]=o++; cy--;
        rep(j,4){
            O[cx][cy]=o++;
            cy--;
            O[cx][cy]=o++;
            cy--;
            O[cx][cy]=o++;
            cx--;
            O[cx][cy]=o++;
            cy++;
            O[cx][cy]=o++;
            cy++;
            O[cx][cy]=o++;
            cx--;
        }
        O[cx][cy]=o++; cy--;
        O[cx][cy]=o++; cy--;
        O[cx][cy]=o++; cy--;
    }
    rep(i,N)rep(j,N){
        iO[O[i][j]]={i,j};
    }
}

vector<pair<int,int>> get_clz_use(int clz_target){
    sort(order.begin(),order.end(),[&](auto a, auto b){
        int da = abs(a.first - cx) + abs(a.second - cy);
        int db = abs(b.first - cx) + abs(b.second - cy);
        int damax = max(abs(a.first - cx), abs(a.second - cy));
        int dbmax = max(abs(b.first - cx), abs(b.second - cy));
        return damax == dbmax ? da < db : damax < dbmax;
    });
    for(uint32_t use_bit=0;use_bit<(1u<<16);++use_bit){
        uint32_t ns = s;
        rep(i,16)if(use_bit>>i&1){
            ns ^= A[order[i].first][order[i].second];
        }
        if(clz20(ns)!=clz_target) continue;
        vector<pair<int,int>> res;
        rep(i,16)if(use_bit>>i&1){
            res.emplace_back(order[i]);
        }
        return res;
    }
    cerr << "No use found!" << endl;
    return {};
}

vector<pair<int,int>> get_clz_use(int clz_target, int gx, int gy){
    sort(order.begin(),order.end(),[&](auto a, auto b){
        int da = abs(a.first - gx) + abs(a.second - gy);
        int db = abs(b.first - gx) + abs(b.second - gy);
        int damax = max(abs(a.first - gx), abs(a.second - gy));
        int dbmax = max(abs(b.first - gx), abs(b.second - gy));
        return damax == dbmax ? da < db : damax < dbmax;
    });
    for(uint32_t use_bit=0;use_bit<(1u<<16);++use_bit){
        uint32_t ns = s ^ A[gx][gy];
        rep(i,16)if(use_bit>>i&1){
            ns ^= A[order[i].first][order[i].second];
        }
        if(clz20(ns)!=clz_target) continue;
        vector<pair<int,int>> res;
        rep(i,16)if(use_bit>>i&1){
            res.emplace_back(order[i]);
        }
        return res;
    }
    cerr << "No use found!" << endl;
    return {};
}

void go_to(int gx, int gy){
    while(cx<gx){
        Out+='D';
        ++cx;
    }
    while(cx>gx){
        Out+='U';
        --cx;
    }
    while(cy<gy){
        Out+='R';
        ++cy;
    }
    while(cy>gy){
        Out+='L';
        --cy;
    }
}

void copy_s(){
    s ^= A[cx][cy];
    Out+='C';
    cerr << "Copying A[" << cx << "][" << cy << "] = " << (A[cx][cy]) << endl;
    cerr << (s^A[cx][cy]) << " -> " << s << endl;
}

void write_s(){
    A[cx][cy] ^= s;
    Out+='W';
}

// Manhattan distance
int mht(const pair<int,int>& a, const pair<int,int>& b){
    return abs(a.first - b.first) + abs(a.second - b.second);
};

string print_bit(uint32_t x){
    string res;
    rep(i,20){
        res += ((x>>(19-i))&1) ? '1' : '0';
    }
    return res;
}

void use_step(const vector<pair<int,int>>& use){
    // insert tsp
    vector<pair<int,int>> path;
    path.emplace_back(cx,cy);
    for(auto p: use){
        int best_diff = 1e9;
        int best_pos = -1;
        rep(i,path.size()){
            int prev_dist = i==path.size()-1 ? 0: mht(path[i], path[i+1]);
            int new_dist = mht(path[i], p) + (i==path.size()-1 ? 0 : mht(p, path[i+1]));
            int diff = new_dist - prev_dist;
            if(diff<best_diff){
                best_diff = diff;
                best_pos = i+1;
            }
        }
        path.insert(path.begin()+best_pos, p);
    }
    cerr << "use size: " << use.size() << ", path size: " << path.size() << endl;

    rep(i,1,path.size()){
        go_to(path[i].first, path[i].second);
        copy_s();
    }
    cerr << "clz used: " << clz20(s) << " s = " << print_bit(s) << endl;
}

void write_step(){
    int start_order = O[cx][cy];
    rep(d,NN){
        int no = (start_order + d) % NN;
        auto [nx, ny] = iO[no];
        if(nx < 3 && ny < 3) continue;
        uint32_t a = A[nx][ny];
        uint32_t na = a ^ s;
        if(a<na){
            go_to(nx, ny);
            write_s();
        }
    }
}

void print_A(){
    rep(i,N)rep(j,N){
        rep(k,20) cerr << ((A[i][j]>>(19-k))&1);
        cerr << (j==N-1?"\n":" ");
    }
}


int main(){
    library::fast_io();
    input.get();

    init_O();
    rep(i,N)rep(j,N){
        cerr << (O[i][j] < 10 ? " " : "") << O[i][j] << (j==N-1?"\n":" ");
    }

    rep(clz_target,9){
        go_to(min(3, cx), min(3, cy));
        auto clz_use = get_clz_use(clz_target);
        use_step(clz_use);
        write_step();
        cerr << Out.size() << " steps after clz " << clz_target << endl;
    }

    rep(i,3)rep(j,3){
        uint32_t a = A[i][j];
        uint32_t ma = a;
        uint32_t max_bit = 0;
        for(int bit=0;bit<512;++bit){
            uint32_t na = s^a;
            rep(k,3)rep(l,3)if(bit&(1<<(k*3+l))){
                na ^= A[k][l];
            }
            if(na>ma){
                ma = na;
                max_bit = bit;
            }
        }
        rep(k,3)rep(l,3)if(max_bit&(1<<(k*3+l))){
            go_to(k,l);
            copy_s();
        }
        go_to(i,j);
        write_s();
    }
    
    
    print_A();
    cerr << Out.size() << " steps in total" << endl;

    if(Out.size()>T){
        Out = Out.substr(0,T);
    }
    for(char c: Out){
        cout << c<<endl;
    }

    cerr << "Total score: ";
    uint64_t score = 0;
    rep(i,N)rep(j,N){
        score += A[i][j];
    }
    cerr << score << endl;

    return 0;
}