結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 Ang1077
|
| 提出日時 | 2025-07-26 16:20:40 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,984 ms / 2,000 ms |
| コード長 | 13,973 bytes |
| コンパイル時間 | 4,405 ms |
| コンパイル使用メモリ | 346,012 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,190,206,004 |
| 最終ジャッジ日時 | 2025-07-26 16:22:29 |
| 合計ジャッジ時間 | 107,705 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
// #pragma GCC optimize
// "-O3,omit-frame-pointer,inline,unroll-all-loops,fast-math" #pragma GCC target
// "tune=native"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// ==== 型・ユーティリティ ====
using u8 = uint8_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i64 = long long;
struct RNG {
uint64_t s[2];
RNG() { reset(time(0)); }
void reset(uint64_t seed) {
auto sm = [s = seed]() mutable {
s += 0x9E3779B97f4A7C15;
u64 z = s;
z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9;
z = (z ^ (z >> 27)) * 0x94D049BB133111EB;
return z ^ (z >> 31);
};
s[0] = sm();
s[1] = sm();
}
static inline uint64_t rotl(uint64_t x, int k) {
return (x << k) | (x >> (64 - k));
}
uint64_t next() {
uint64_t s0 = s[0], s1 = s[1];
uint64_t r = rotl(s0 * 5, 7) * 9;
s1 ^= s0;
s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16);
s[1] = rotl(s1, 37);
return r;
}
double randomDouble() { return (double)(uint32_t)next() / 4294967296.0; }
uint32_t random32(uint32_t r) {
return (uint64_t)(uint32_t)next() * r >> 32;
}
} rng;
struct timer {
chrono::high_resolution_clock::time_point t0;
timer() { t0 = chrono::high_resolution_clock::now(); }
float elapsed() const {
return chrono::duration<float>(chrono::high_resolution_clock::now() -
t0)
.count();
}
};
// ==== シミュレータ ====
struct EvalResult {
u64 sum = 0;
vector<char> ops;
vector<u32> A;
};
struct Simulator {
int N, T, NN; // N=10, NN=100
vector<u32> A0; // 平坦化 A[NN]
vector<int> x, y; // 各 id の座標
vector<int> dist; // dist[a*NN+b]
array<vector<int>, 20> msb_bucket; // 値のMSBごとのid
array<array<vector<int>, 20>, 100> near_msb; // near_msb[t][b] 上位L候補
// 作業状態（simulateごとにリセット）
vector<u32> A;
vector<char> ops;
bitset<100> written;
int cur; // 現在位置 id
u32 s; // レジスタ
int used;
bool store_ops; // 出力をpushするか
inline int DID(int a, int b) const { return dist[a * NN + b]; }
// --- 構築 ---
void init_precompute(int N_, int T_, const vector<vector<u32>> &A2d,
int L = 12) {
N = N_;
T = T_;
NN = N * N;
A0.resize(NN);
x.resize(NN);
y.resize(NN);
int id = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
A0[id] = A2d[i][j];
x[id] = i;
y[id] = j;
++id;
}
// dist 前計算
dist.assign(NN * NN, 0);
for (int a = 0; a < NN; a++)
for (int b = 0; b < NN; b++)
dist[a * NN + b] = abs(x[a] - x[b]) + abs(y[a] - y[b]);
// msb_bucket
for (int b = 0; b < 20; b++)
msb_bucket[b].clear();
for (int i = 0; i < NN; i++) {
u32 v = A0[i];
if (v == 0)
continue;
int b = 31 - __builtin_clz(v);
if (b >= 0 && b < 20)
msb_bucket[b].push_back(i);
}
// near_msb（ターゲットごと・各msbで近い順に上位L）
for (int t = 0; t < NN; t++) {
for (int b = 0; b < 20; b++) {
auto &bucket = msb_bucket[b];
if (bucket.empty()) {
near_msb[t][b].clear();
continue;
}
// ソートはコスト、なので上位Lのみ partial_sort
vector<int> tmp = bucket;
auto cmp = [&](int p, int q) { return DID(p, t) < DID(q, t); };
if ((int)tmp.size() > L) {
nth_element(tmp.begin(), tmp.begin() + L, tmp.end(), cmp);
tmp.resize(L);
sort(tmp.begin(), tmp.end(), cmp);
} else {
sort(tmp.begin(), tmp.end(), cmp);
}
near_msb[t][b] = move(tmp);
}
}
}
// --- 低レベル操作 ---
inline void move_to(int to) {
int d = DID(cur, to);
if (store_ops) {
// 実際のUDLRは省略（必要なら復元可能だが高速化のため省く）
// ただし制約上はUDLRを出力する必要があるため、bestのみ後で emit
// する
}
used += d;
cur = to;
}
inline void opC() {
used += 1;
if (store_ops)
ops.push_back('C');
}
inline void opW() {
used += 1;
if (store_ops)
ops.push_back('W');
}
inline bool can_spend(int c) const { return used + c <= T; }
// emit 用：best のときにだけ UDLR を展開して出力する実装（簡易）
void emit_move_path(int from, int to) {
int dr = x[to] - x[from], dc = y[to] - y[from];
char ch = (dr > 0 ? 'D' : 'U');
for (int k = 0; k < abs(dr); k++) {
ops.push_back(ch);
}
ch = (dc > 0 ? 'R' : 'L');
for (int k = 0; k < abs(dc); k++) {
ops.push_back(ch);
}
}
// 0C/1C の最良手を返す（value, cost, mode, pr）
struct Cand {
long long val;
int cost;
int mode;
int pr;
};
inline Cand best_action_for_target(int t) {
Cand best{LLONG_MIN, INT_MAX, -1, -1};
int rem = T - used;
// 0C
{
int c0 = DID(cur, t) + 1;
if (c0 <= rem) {
u32 nv = (A[t] ^ s);
if ((long long)nv > (long long)A[t]) {
best = {(long long)nv, c0, 0, -1};
}
}
}
// 1C（枝刈り：最上位0ビットに効く MSB バケットの上位Lのみ）
u32 base = A[t] ^ s;
int k = -1;
for (int b = 19; b >= 0; --b) {
if (((base >> b) & 1u) == 0u) {
k = b;
break;
}
}
if (k >= 0) {
auto const &cand = near_msb[t][k];
for (int pr : cand) {
int c1 = DID(cur, pr) + 1 + DID(pr, t) + 1;
if (c1 > rem)
continue;
u32 s2 = s ^ A[pr];
u32 nv = (A[t] ^ s2);
if ((long long)nv <= (long long)A[t])
continue;
if (nv > best.val || (nv == best.val && c1 < best.cost)) {
best = {(long long)nv, c1, 1, pr};
}
}
// フォールバック：次位ビット
if (best.mode < 0 && k > 0) {
auto const &cand2 = near_msb[t][k - 1];
for (int pr : cand2) {
int c1 = DID(cur, pr) + 1 + DID(pr, t) + 1;
if (c1 > rem)
continue;
u32 s2 = s ^ A[pr];
u32 nv = (A[t] ^ s2);
if ((long long)nv <= (long long)A[t])
continue;
if (nv > best.val || (nv == best.val && c1 < best.cost)) {
best = {(long long)nv, c1, 1, pr};
}
}
}
}
return best; // mode==-1 なら改善不可
}
// 訪問順固定で評価
EvalResult simulate_with_order(const vector<int> &order,
bool need_store_ops) {
// リセット
A = A0;
ops.clear();
written.reset();
cur = 0;
s = 0;
used = 0;
store_ops = false;
// 探索（出力は貯めない）
bool progressed = true;
while (progressed && used < T) {
progressed = false;
for (int id : order) {
if (used >= T)
break;
if (written.test(id))
continue;
auto cand = best_action_for_target(id);
if (cand.mode < 0)
continue; // 改善なし
// 実行（emitなし）
if (cand.mode == 0) {
if (!can_spend(cand.cost))
continue;
move_to(id);
opW();
A[id] ^= s;
written.set(id);
progressed = true;
} else {
if (!can_spend(cand.cost))
continue;
move_to(cand.pr);
opC();
s ^= A[cand.pr];
move_to(id);
opW();
A[id] ^= s;
written.set(id);
progressed = true;
}
}
}
// sum
EvalResult res;
res.sum = 0;
for (int i = 0; i < NN; i++)
res.sum += A[i];
// ベスト更新用に ops と最終盤面が必要なら、もう一度 emit 付きで再生
if (need_store_ops) {
// もう一度シミュレート（出力あり）
vector<u32> A_goal = A;
bitset<100> W_goal = written;
// 再生
A = A0;
ops.clear();
written.reset();
cur = 0;
s = 0;
used = 0;
store_ops = true;
progressed = true;
while (progressed && used < T) {
progressed = false;
for (int id : order) {
if (used >= T)
break;
if (W_goal.test(id) == false)
continue; // 最終でWしたセルだけ再現
auto cand = best_action_for_target(id);
if (cand.mode < 0)
continue;
if (!can_spend(cand.cost))
continue;
// emit move
emit_move_path(cur, (cand.mode == 0 ? id : cand.pr));
move_to((cand.mode == 0
? id
: cand.pr)); // usedは重複加算になるので注意
// ↑ move_to が used を加算するため、emit_move_path 後は
// move_to で used 加算されます。emit_move_path は純出力。
if (cand.mode == 1) {
ops.push_back('C');
s ^= A[cand.pr];
++used;
}
emit_move_path(cur, id);
move_to(id);
ops.push_back('W');
++used;
A[id] ^= s;
written.set(id);
progressed = true;
}
}
res.ops = ops;
res.A = A_goal; // 文字列は完全一致でなくても、W
// した結果だけ一致していればOK
}
return res;
}
};
// ==== メイン（焼きなまし：隣接スワップ＋一点挿入）====
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, T;
if (!(cin >> N >> T))
return 0;
vector<vector<u32>> A2(N, vector<u32>(N));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> A2[i][j];
Simulator sim;
sim.init_precompute(N, T, A2, /*L=*/12);
vector<int> order(sim.NN);
iota(order.begin(), order.end(), 0);
timer tim;
const double LIM = 1.98;
const double T0 = 1e8, T1 = 1e-3;
EvalResult cur = sim.simulate_with_order(order, /*need_store_ops=*/false);
EvalResult best = cur;
vector<int> best_order = order;
while (tim.elapsed() < LIM) {
// 温度
double ft = tim.elapsed() / LIM;
double temp = T0 * pow(T1 / T0, ft);
// 近傍生成：隣接スワップ or 一点挿入
vector<int> cand = order;
if (rng.random32(2)) {
int i = rng.random32((uint32_t)max(1, (int)cand.size() - 1));
swap(cand[i], cand[i + 1]);
} else {
int n = (int)cand.size();
int i = rng.random32((uint32_t)n);
int j = rng.random32((uint32_t)(n - 1));
if (j >= i)
++j;
int v = cand[i];
if (i < j) {
for (int k = i; k < j; k++)
cand[k] = cand[k + 1];
cand[j] = v;
} else {
for (int k = i; k > j; k--)
cand[k] = cand[k - 1];
cand[j] = v;
}
}
EvalResult cand_res =
sim.simulate_with_order(cand, /*need_store_ops=*/false);
long long delta = (long long)cand_res.sum - (long long)cur.sum;
bool accept = (delta >= 0) || (rng.randomDouble() < exp(delta / temp));
if (accept) {
order.swap(cand);
cur = cand_res;
if (cand_res.sum > best.sum) {
best = sim.simulate_with_order(
order, /*need_store_ops=*/true); // emit 付き
best_order = order;
}
}
}
// --- デバッグ出力 ---
cerr << best.ops.size() << '\n';
u64 sum = 0;
for (int i = 0; i < sim.NN; i++) {
cerr << best.A[i] << ((i % N == N - 1) ? '\n' : ' ');
sum += best.A[i];
}
cerr << sum << '\n';
// --- 解の出力 ---
for (char ch : best.ops)
cout << ch << '\n';
return 0;
}