結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 Ang1077
|
| 提出日時 | 2025-07-26 16:10:16 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,983 ms / 2,000 ms |
| コード長 | 16,612 bytes |
| コンパイル時間 | 4,472 ms |
| コンパイル使用メモリ | 336,288 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,169,178,646 |
| 最終ジャッジ日時 | 2025-07-26 16:12:06 |
| 合計ジャッジ時間 | 107,673 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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 <experimental/simd>
// INCLUDE <atcoder/all>
#include <ext/pb_ds/assoc_container.hpp>
// #include <immintrin.h>
// #include <sys/time.h>
// #include <x86intrin.h>
using namespace std;
// Macros
#define el '\n'
#define all(v) (v).begin(), (v).end()
using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
#define rep(i, n) for (i64 i = 0; i < (i64)(n); i++)
template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T> using max_queue = priority_queue<T>;
struct uint64_hash {
static inline uint64_t rotr(uint64_t x, unsigned k) {
return (x >> k) | (x << (8U * sizeof(uint64_t) - k));
}
static inline uint64_t hash_int(uint64_t x) noexcept {
auto h1 = x * (uint64_t)(0xA24BAED4963EE407);
auto h2 = rotr(x, 32U) * (uint64_t)(0x9FB21C651E98DF25);
auto h = rotr(h1 + h2, 32U);
return h;
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM =
std::chrono::steady_clock::now().time_since_epoch().count();
return hash_int(x + FIXED_RANDOM);
}
};
template <typename K, typename V, typename Hash = uint64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;
template <typename K, typename Hash = uint64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;
// Constant
constexpr bool DEBUG = false;
const double pi = 3.141592653589793238;
const i32 inf32 = 1073741823;
const i64 inf64 = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
const int MOD = 998244353;
const array<int, 8> dx = {0, 0, -1, 1, -1, -1, 1, 1};
const array<int, 8> dy = {-1, 1, 0, 0, -1, 1, -1, 1};
// Printing (optional)
template <class T> void print_collection(ostream &out, T const &x);
template <class T, size_t... I>
void print_tuple(ostream &out, T const &a, index_sequence<I...>);
namespace std {
template <class... A> ostream &operator<<(ostream &out, tuple<A...> const &x) {
print_tuple(out, x, index_sequence_for<A...>{});
return out;
}
template <class... A> ostream &operator<<(ostream &out, pair<A...> const &x) {
print_tuple(out, x, index_sequence_for<A...>{});
return out;
}
template <class A, size_t N>
ostream &operator<<(ostream &out, array<A, N> const &x) {
print_collection(out, x);
return out;
}
template <class A> ostream &operator<<(ostream &out, vector<A> const &x) {
print_collection(out, x);
return out;
}
template <class A> ostream &operator<<(ostream &out, deque<A> const &x) {
print_collection(out, x);
return out;
}
template <class A> ostream &operator<<(ostream &out, multiset<A> const &x) {
print_collection(out, x);
return out;
}
template <class A, class B>
ostream &operator<<(ostream &out, multimap<A, B> const &x) {
print_collection(out, x);
return out;
}
template <class A> ostream &operator<<(ostream &out, set<A> const &x) {
print_collection(out, x);
return out;
}
template <class A, class B>
ostream &operator<<(ostream &out, map<A, B> const &x) {
print_collection(out, x);
return out;
}
template <class A>
ostream &operator<<(ostream &out, unordered_set<A> const &x) {
print_collection(out, x);
return out;
}
} // namespace std
template <class T, size_t... I>
void print_tuple(ostream &out, T const &a, index_sequence<I...>) {
using swallow = int[];
out << '(';
(void)swallow{0, (void(out << (I == 0 ? "" : ", ") << get<I>(a)), 0)...};
out << ')';
}
template <class T> void print_collection(ostream &out, T const &x) {
int f = 0;
out << '[';
for (auto const &i : x) {
out << (f++ ? "," : "");
out << i;
}
out << "]";
}
// Random
struct RNG {
uint64_t s[2];
RNG(u64 seed) { reset(seed); }
RNG() { reset(time(0)); }
using result_type = u32;
constexpr u32 min() { return numeric_limits<u32>::min(); }
constexpr u32 max() { return numeric_limits<u32>::max(); }
u32 operator()() { return randomInt32(); }
static __attribute__((always_inline)) inline uint64_t rotl(const uint64_t x,
int k) {
return (x << k) | (x >> (64 - k));
}
inline void reset(u64 seed) {
struct splitmix64_state {
u64 s;
u64 splitmix64() {
u64 result = (s += 0x9E3779B97f4A7C15);
result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;
result = (result ^ (result >> 27)) * 0x94D049BB133111EB;
return result ^ (result >> 31);
}
};
splitmix64_state sm{seed};
s[0] = sm.splitmix64();
s[1] = sm.splitmix64();
}
uint64_t next() {
const uint64_t s0 = s[0];
uint64_t s1 = s[1];
const uint64_t result = rotl(s0 * 5, 7) * 9;
s1 ^= s0;
s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16); // a, b
s[1] = rotl(s1, 37); // c
return result;
}
inline u32 randomInt32() { return (u32)next(); }
inline u64 randomInt64() { return next(); }
inline u32 random32(u32 r) { return (((u64)randomInt32()) * r) >> 32; }
inline u64 random64(u64 r) { return randomInt64() % r; }
inline u32 randomRange32(u32 l, u32 r) { return l + random32(r - l + 1); }
inline u64 randomRange64(u64 l, u64 r) { return l + random64(r - l + 1); }
inline double randomDouble() {
return (double)randomInt32() / 4294967296.0;
}
inline float randomFloat() { return (float)randomInt32() / 4294967296.0; }
inline double randomRangeDouble(double l, double r) {
return l + randomDouble() * (r - l);
}
template <class T> void shuffle(vector<T> &v) {
i32 sz = (i32)v.size();
for (i32 i = sz; i > 1; i--) {
i32 p = random32(i);
swap(v[i - 1], v[p]);
}
}
template <class T> void shuffle(T *fr, T *to) {
i32 sz = (i32)distance(fr, to);
for (int i = sz; i > 1; i--) {
int p = random32(i);
swap(fr[i - 1], fr[p]);
}
}
template <class T> inline int sample_index(vector<T> const &v) {
return random32((u32)v.size());
}
template <class T> inline T sample(vector<T> const &v) {
return v[sample_index(v)];
}
} rng;
// Timer
struct timer {
chrono::high_resolution_clock::time_point t_begin;
timer() { t_begin = chrono::high_resolution_clock::now(); }
void reset() { t_begin = chrono::high_resolution_clock::now(); }
float elapsed() const {
return chrono::duration<float>(chrono::high_resolution_clock::now() -
t_begin)
.count();
}
};
// Bits helpers
__attribute__((always_inline)) inline u64 bit(u64 x) { return 1ull << x; }
struct EvalResult {
u64 sum = 0;
vector<char> ops;
vector<vector<u32>> A;
};
struct Simulator {
int N, T;
vector<vector<u32>> A0;
// working state
vector<vector<u32>> A;
vector<char> ops;
vector<u8> written; // each cell W at most once
int r, c; // 0-indexed
u32 s; // current s (register)
int used;
inline int idx(int i, int j) const { return i * N + j; }
inline int manhattan(int r1, int c1, int r2, int c2) const {
return abs(r1 - r2) + abs(c1 - c2);
}
inline void move_to(int tr, int tc) {
while (r < tr) {
ops.push_back('D');
++r;
++used;
}
while (r > tr) {
ops.push_back('U');
--r;
++used;
}
while (c < tc) {
ops.push_back('R');
++c;
++used;
}
while (c > tc) {
ops.push_back('L');
--c;
++used;
}
}
inline bool can_spend(int cost) const { return used + cost <= T; }
// simulate with a fixed visiting order; within each target: choose 0C or 1C
// (best) under remaining turns.
EvalResult simulate_with_order(const vector<int> &order,
bool store_ops_matrix) {
// reset state
A = A0;
if (store_ops_matrix) {
ops.clear();
ops.reserve(5000);
} else {
// still need to collect ops to count used moves; but we can avoid
// storing by using a dummy buffer
ops.clear();
ops.reserve(16);
}
written.assign(N * N, 0);
r = 0;
c = 0;
s = 0;
used = 0;
bool progressed = true;
while (progressed && used < T) {
progressed = false;
for (int id : order) {
if (used >= T)
break;
int wr = id / N, wc = id % N;
if (written[id])
continue;
int rem = T - used;
// Option 0C
long long best_new_val_0 = LLONG_MIN;
int cost0 = manhattan(r, c, wr, wc) + 1;
if (cost0 <= rem) {
u32 new_val = (A[wr][wc] ^ s);
if ((long long)new_val > (long long)A[wr][wc]) {
best_new_val_0 = new_val;
}
}
// Option 1C
long long best_new_val_1 = LLONG_MIN;
int best_pr = -1, best_pc = -1, best_cost1 = 0;
for (int pr = 0; pr < N; ++pr) {
for (int pc = 0; pc < N; ++pc) {
int total_cost = manhattan(r, c, pr, pc) + 1 +
manhattan(pr, pc, wr, wc) + 1;
if (total_cost > rem)
continue;
u32 s2 = s ^ A[pr][pc];
u32 new_val = (A[wr][wc] ^ s2);
if ((long long)new_val > (long long)A[wr][wc]) {
if ((long long)new_val > best_new_val_1 ||
((long long)new_val == best_new_val_1 &&
total_cost < best_cost1)) {
best_new_val_1 = new_val;
best_pr = pr;
best_pc = pc;
best_cost1 = total_cost;
}
}
}
}
// pick better action (by resulting value; tie -> cheaper; tie
// -> 0C優先)
int mode = -1; // 0=0C,1=1C
int chosen_cost = 0;
if (best_new_val_0 == LLONG_MIN &&
best_new_val_1 == LLONG_MIN) {
continue; // cannot improve this target within budget
} else if (best_new_val_0 != LLONG_MIN &&
best_new_val_1 == LLONG_MIN) {
mode = 0;
chosen_cost = cost0;
} else if (best_new_val_0 == LLONG_MIN &&
best_new_val_1 != LLONG_MIN) {
mode = 1;
chosen_cost = best_cost1;
} else {
if (best_new_val_1 > best_new_val_0) {
mode = 1;
chosen_cost = best_cost1;
} else if (best_new_val_1 < best_new_val_0) {
mode = 0;
chosen_cost = cost0;
} else {
if (best_cost1 < cost0) {
mode = 1;
chosen_cost = best_cost1;
} else {
mode = 0;
chosen_cost = cost0;
}
}
}
// execute
if (mode == 0) {
if (!can_spend(chosen_cost))
continue;
move_to(wr, wc);
ops.push_back('W');
++used;
A[wr][wc] ^= s;
written[id] = 1;
progressed = true;
} else {
if (!can_spend(chosen_cost))
continue;
move_to(best_pr, best_pc);
ops.push_back('C');
++used;
s ^= A[best_pr][best_pc];
move_to(wr, wc);
ops.push_back('W');
++used;
A[wr][wc] ^= s;
written[id] = 1;
progressed = true;
}
}
}
EvalResult res;
res.sum = 0;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
res.sum += A[i][j];
if (store_ops_matrix) {
res.ops = ops;
res.A = A;
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, T;
if (!(cin >> N >> T))
return 0;
vector<vector<u32>> A(N, vector<u32>(N));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
cin >> A[i][j];
Simulator sim;
sim.N = N;
sim.T = T;
sim.A0 = A;
// initial order: row-major
vector<int> order(N * N);
iota(order.begin(), order.end(), 0);
timer tim;
// Evaluate initial order
EvalResult cur = sim.simulate_with_order(order, false);
EvalResult best = cur;
vector<int> best_order = order;
// SA params
const double TIME_LIMIT = 1.98; // seconds
const double T0 = 1e8; // initial temperature
const double T1 = 1e-3; // final temperature
int iters = 0;
while (true) {
double t = tim.elapsed();
if (t >= TIME_LIMIT)
break;
++iters;
// temperature schedule (exponential)
double temp = T0 * pow(T1 / T0, t / TIME_LIMIT);
// generate neighbor by adjacent swap or 1-point insertion
vector<int> cand_order = order;
if (rng.random32(2)) {
// adjacent swap
int i = rng.random32((u32)max(1, (int)cand_order.size() - 1));
swap(cand_order[i], cand_order[i + 1]);
} else {
// 1-point insertion
int n = (int)cand_order.size();
int i = rng.random32((u32)n);
int j = rng.random32((u32)(n - 1));
if (j >= i)
++j; // ensure j != i
int v = cand_order[i];
if (i < j) {
for (int k = i; k < j; ++k)
cand_order[k] = cand_order[k + 1];
cand_order[j] = v;
} else {
for (int k = i; k > j; --k)
cand_order[k] = cand_order[k - 1];
cand_order[j] = v;
}
}
// evaluate neighbor (no need to store ops/A unless it's new global
// best)
EvalResult cand = sim.simulate_with_order(cand_order, false);
long long delta = (long long)cand.sum - (long long)cur.sum;
bool accept = false;
if (delta >= 0) {
accept = true;
} else {
double prob = exp(delta / temp);
double r = rng.randomDouble();
if (r < prob)
accept = true;
}
if (accept) {
order.swap(cand_order);
cur = cand;
if (cand.sum > best.sum) {
cerr << iters << " " << best.sum << '\n';
// store full best (ops + A)
EvalResult full = sim.simulate_with_order(order, true);
best = full;
best_order = order;
}
}
}
// --- デバッグ出力（stderr） ---
cerr << best.ops.size() << '\n';
u64 out_sum = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cerr << best.A[i][j] << " ";
out_sum += best.A[i][j];
}
cerr << '\n';
}
cerr << out_sum << '\n';
// --- 解の出力（stdout） ---
for (char ch : best.ops)
cout << ch << '\n';
return 0;
}