結果

問題 No.5022 XOR Printer
ユーザー syndrome
提出日時 2025-07-26 14:29:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 6,474 bytes
コンパイル時間 4,075 ms
コンパイル使用メモリ 329,352 KB
実行使用メモリ 7,716 KB
スコア 4,998,236,120
最終ジャッジ日時 2025-07-26 14:29:53
合計ジャッジ時間 6,016 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

// (◕ᴗ◕✿)

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define srep(i, s, n) for (ll i = s; i < (n); ++i)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = 3.141592653589793;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;

#define debug(var)  do{std::cout << #var << " : \n";view(var);}while(0)
template<typename T> void view(T e){cout << e << endl;}
template<typename T> void view(const vc<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;}
template<typename T> void view(const vv<T>& vv){ for(const auto& v : vv){ view(v); } }

// #define DEBUG

#ifdef DEBUG
constexpr bool DEBUGMODE = true;
#else
constexpr bool DEBUGMODE = false;
#endif

ofstream wrt;
string outputfile = "output.txt", inputfile = "input.txt";


unsigned int randxor(){
    static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned int t;
    t = (x ^ (x << 11)); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int randint(int a, int b) {return(a + randxor() % (b - a));}

struct Timer {
    public:
        Timer(int limit){
            start = chrono::high_resolution_clock::now();
            goal = start + chrono::milliseconds(limit);
        }

        inline double rate(){
            return (chrono::high_resolution_clock::now() - start).count() / (double)(goal - start).count();
        }

        inline int get_time(){return (chrono::high_resolution_clock::now() - start).count() / 1e6;}

    private:
        chrono::high_resolution_clock::time_point start;
        chrono::high_resolution_clock::time_point goal;  
};

ll hilbertorder(int x, int y, ll maxn) {
  ll rx, ry, d = 0;
  for (ll s = maxn >> 1; s; s >>= 1) {
    rx = (x & s)>0, ry = (y & s)>0;
    d += s * s * ((rx * 3) ^ ry);
    if (ry) continue;
    if (rx) {
      x = maxn - 1 - x;
      y = maxn - 1 - y;
    }
    swap(x, y);
  }
  return d;
}

double log_table[70000];
//variable
constexpr int TIME_LIMIT = 2990;
constexpr int N = 10;
constexpr int M = 100;
constexpr int T = 1000;
array<int, M> A;
vi topbit[20];
array<int, M> eval;

struct Solver{
    void input(){
        if (DEBUGMODE){
            ifstream in(inputfile);
            cin.rdbuf(in.rdbuf());
            int a; cin >> a >> a;
            rep(i, M) cin >> A[i];
        }else{
            int a; cin >> a >> a;
            rep(i, M) cin >> A[i];
        }
    }

    void init(){
		double n = 1 / (double)(2 * 70000);
		for (int i = 0; i < 70000; i++) {
			log_table[i] = log(((double)i / 70000) + n);
		}

        rep(i, M) topbit[31 - __builtin_clz(A[i])].push_back(i);
        ll maxn = 1;
        while (maxn < N) maxn <<= 1;
        rep(i, M) eval[i] = hilbertorder(i / N, i % N, maxn);
    }

    pair<int, vvi> greedy(vi indexs){
        int P = len(indexs);
        vi S(1, A[indexs[0]]);
        srep(i, 1, len(indexs)) S.push_back(S.back() ^ A[indexs[i]]);
        vvi paths(P);
        rep(i, P) paths[i].push_back(indexs[i]);
        int score = 0;
        vi cmbs(1 << P, 0);
        rep(i, 1 << P){
            rep(j, P) if (i >> j & 1) cmbs[i] ^= S[j];
        }
        vi mark(M, 0);
        rep(i, P) mark[indexs[i]] = i + 1;
        rep(i, M){
            int mask = (1 << mark[i]) - 1;
            int best = -1, bestcmb = -1;
            rep(cmb, 1 << P) if ((mask & cmb) == 0 && (A[i] ^ cmbs[cmb]) > best){
                best = A[i] ^ cmbs[cmb];
                bestcmb = cmb;
            }
            rep(j, P) if (bestcmb >> j & 1) paths[j].push_back(i);
            score += best;
            // cout << bestcmb << ' ';
            // if (i % N == N - 1) cout << endl;
        }
        return {score, paths};
    }

    void move(int s, int t){
        if (DEBUGMODE){
            while (s / N < t / N){
                wrt << 'D' << endl;
                s += N;
            }
            while (s / N > t / N){
                wrt << 'U' << endl;
                s -= N;
            }
            while (s % N < t % N){
                wrt << 'R' << endl;
                s++;
            }
            while (s % N > t % N){
                wrt << 'L' << endl;
                s--;
            }
        }else{
            while (s / N < t / N){
                cout << 'D' << endl;
                s += N;
            }
            while (s / N > t / N){
                cout << 'U' << endl;
                s -= N;
            }
            while (s % N < t % N){
                cout << 'R' << endl;
                s++;
            }
            while (s % N > t % N){
                cout << 'L' << endl;
                s--;
            }
        }
    }

    void output(vvi path){
        rep(p, len(path)){
            int frst = path[p][0];
            sort(all(path[p]), [&](auto i, auto j){ return eval[i] < eval[j];});
            int id = 0;
            rep(i, len(path[p])) if (path[p][i] == frst){id = i; break;}
            rotate(path[p].begin(), path[p].begin() + id, path[p].end());
        }
        
        int pos = 0;
        for (auto p : path){
            rep(i, len(p)){
                move(pos, p[i]);
                pos = p[i];
                if (DEBUGMODE){
                    if (i == 0) wrt << 'C' << endl;
                    else wrt << 'W' << endl;
                }else{
                    if (i == 0) cout << 'C' << endl;
                    else cout << 'W' << endl;
                }
            }
        }
    }

    void run(){
        Timer timer(TIME_LIMIT);
        input();
        init();
        vi indexs = {topbit[17][0], topbit[18][0], topbit[19][0], topbit[19][1]};
        auto [score, ans] = greedy(indexs);
        // cout << score << endl;
        output(ans);
    }
};

int main(){
    wrt.open(outputfile, ios::out);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Solver solver;
    solver.run();
    wrt.close();
    return 0;
}
0