結果
| 問題 | No.5022 XOR Printer |
| コンテスト | |
| ユーザー |
 mai
|
| 提出日時 | 2025-07-26 16:42:59 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 22 ms / 2,000 ms |
| コード長 | 21,532 bytes |
| コンパイル時間 | 5,007 ms |
| コンパイル使用メモリ | 344,076 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 4,969,693,351 |
| 最終ジャッジ日時 | 2025-07-26 16:43:08 |
| 合計ジャッジ時間 | 7,712 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// clang-format off
using namespace std;
using ll = long long int;
#define all(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(typename remove_const<typename remove_reference<decltype(l)>::type>::type cnt={};(cnt)<(l);++(cnt))
#define rrepeat(cnt,l) for(auto cnt=(l)-1;0<=(cnt);--(cnt))
#define iterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);++(cnt))
#define upto(cnt,b,e,step) for(auto cnt=(b);(cnt)<=(e);(cnt)+=(step))
#define downto(cnt,b,e,step) for(auto cnt=(b);(e)<=(cnt);(cnt)-=(step))
const long long MD = 998244353; const long double PI = 3.1415926535897932384626433832795L;
template<typename T1, typename T2> inline ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << '(' << p.first << ':' << p.second << ')'; return o; }
template<typename T> inline T& chmax(T& to, const T& val) { return to = max(to, val); }
template<typename T> inline T& chmin(T& to, const T& val) { return to = min(to, val); }
void bye(string s, int code = 0) { cout << s << endl; exit(code); }
mt19937_64 randdev(8901016);
template<typename T, typename Random = decltype(randdev), typename enable_if<is_integral<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_int_distribution<T>(l, h)(rand); }
template<typename T, typename Random = decltype(randdev), typename enable_if<is_floating_point<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_real_distribution<T>(l, h)(rand); }template<typename T>
static ostream& operator<<(ostream& o, const std::vector<T>& v) {
o << "[ "; for(const auto& e : v) o<<e<<' '; return o << ']';
}
template <typename I> struct MyRangeFormat{ I b,e; MyRangeFormat(I _b, I _e):b(_b),e(_e){} };
template<typename I> static ostream& operator<<(ostream& o, const MyRangeFormat<I>& f) {
o << "[ "; iterate(i,f.b,f.e) o<<*i<<' '; return o << ']';
}
template <typename I> struct MyMatrixFormat{
const I& p; long long n, m;
MyMatrixFormat(const I& _p, long long _n, long long _m):p(_p),n(_n),m(_m){}
};
template<typename I> static ostream& operator<<(ostream& o, const MyMatrixFormat<I>& f) {
o<<'\n'; repeat(i,(f.n)) { repeat(j,f.m) o<<f.p[i][j]<<' '; o<<'\n'; }
return o;
}
struct LOG_t { ~LOG_t() { clog << endl; } };
#define LOG (LOG_t(),clog<<'L'<<__LINE__<<": ")
#define FMTA(m,w) (MyRangeFormat<decltype(m+0)>(m,m+w))
#define FMTR(b,e) (MyRangeFormat<decltype(e)>(b,e))
#define FMTV(v) FMTR(v.begin(),v.end())
#define FMTM(m,h,w) (MyMatrixFormat<decltype(m+0)>(m,h,w))
#if defined(_WIN32) || defined(_WIN64)
#define getc_x _getc_nolock
#define putc_x _putc_nolock
#elif defined(__GNUC__)
#define getc_x getc_unlocked
#define putc_x putc_unlocked
#else
#define getc_x getc
#define putc_x putc
#endif
class MaiScanner {
FILE* fp_;
constexpr bool isvisiblechar(char c) noexcept { return (0x21<=(c)&&(c)<=0x7E); }
public:
inline MaiScanner(FILE* fp):fp_(fp){}
template<typename T> void input_integer(T& var) noexcept {
var = 0; T sign = 1;
int cc = getc_x(fp_);
for (; cc < '0' || '9' < cc; cc = getc_x(fp_))
if (cc == '-') sign = -1;
for (; '0' <= cc && cc <= '9'; cc = getc_x(fp_))
var = (var << 3) + (var << 1) + cc - '0';
var = var * sign;
}
inline int c() noexcept { return getc_x(fp_); }
template<typename T, typename enable_if<is_integral<T>::value, nullptr_t>::type = nullptr>
inline MaiScanner& operator>>(T& var) noexcept { input_integer<T>(var); return *this; }
inline MaiScanner& operator>>(string& var) {
int cc = getc_x(fp_);
for (; !isvisiblechar(cc); cc = getc_x(fp_));
for (; isvisiblechar(cc); cc = getc_x(fp_))
var.push_back(cc);
return *this;
}
template<typename IT> inline void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; }
};
class MaiPrinter {
FILE* fp_;
public:
inline MaiPrinter(FILE* fp):fp_(fp){}
template<typename T>
void output_integer(T var) noexcept {
if (var == 0) { putc_x('0', fp_); return; }
if (var < 0)
putc_x('-', fp_),
var = -var;
char stack[32]; int stack_p = 0;
while (var)
stack[stack_p++] = '0' + (var % 10),
var /= 10;
while (stack_p)
putc_x(stack[--stack_p], fp_);
}
inline MaiPrinter& operator<<(char c) noexcept { putc_x(c, fp_); return *this; }
template<typename T, typename enable_if<is_integral<T>::value, nullptr_t>::type = nullptr>
inline MaiPrinter& operator<<(T var) noexcept { output_integer<T>(var); return *this; }
inline MaiPrinter& operator<<(const char* str_p) noexcept { while (*str_p) putc_x(*(str_p++), fp_); return *this; }
inline MaiPrinter& operator<<(const string& str) {
const char* p = str.c_str();
const char* l = p + str.size();
while (p < l) putc_x(*p++, fp_);
return *this;
}
template<typename IT> void join(IT begin, IT end, char sep = ' ') { for (bool b = 0; begin != end; ++begin, b = 1) b ? *this << sep << *begin : *this << *begin; }
};
MaiScanner scanner(stdin);
MaiPrinter printer(stdout);
// clang-format on
template <typename C = std::chrono::milliseconds> class Timer {
std::chrono::system_clock::time_point tp_;
public:
static inline auto now() { return std::chrono::system_clock::now(); }
inline void tic() { tp_ = now(); }
inline auto toc() const {
return std::chrono::duration_cast<C>(now() - tp_).count();
}
inline Timer() : tp_(now()) {}
};
inline std::ostream &operator<<(std::ostream &o, const Timer<> &t) {
return o << (long long)t.toc();
}
struct P {
using T = int;
T y, x;
constexpr inline explicit P(T _y, T _x) : y(_y), x(_x) {}
constexpr inline P() : y(0), x(0) {}
constexpr inline bool operator==(P p) const { return y == p.y && x == p.x; }
constexpr inline bool operator!=(P p) const { return y != p.y || x != p.x; }
constexpr inline bool operator<(P p) const { return y == p.y ? x < p.x : y < p.y; }
constexpr inline P operator+(P p) const { return P(y + p.y, x + p.x); }
constexpr inline P operator-(P p) const { return P(y - p.y, x - p.x); }
inline P &operator+=(P p) {
y += p.y;
x += p.x;
return *this;
}
inline P &operator-=(P p) {
y -= p.y;
x -= p.x;
return *this;
}
inline P &operator*=(T m) {
y *= m;
x *= m;
return *this;
}
inline T distM(P p) const { return abs(y - p.y) + abs(x - p.x); }
inline T distC(P p) const { return max(abs(y - p.y), abs(x - p.x)); }
template <typename ITR> ITR nearestM(ITR begin, ITR end) const {
if (begin == end)
return end;
T best = distM(*begin);
ITR besti = begin;
for (ITR it = begin; ++it, it != end;) {
T m = distM(*it);
if (best < m) {
best = m;
besti = it;
}
}
return besti;
}
};
inline ostream &operator<<(ostream &os, P p) {
os << '(' << p.y << ',' << p.x << ')';
return os;
}
const P FourMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1)};
const P FiveMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1), P(0, 0)};
const P EightMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1),
P(-1, -1), P(-1, 1), P(1, -1), P(1, 1)};
inline P operator*(P::T m, P p) noexcept { return P(m * p.y, m * p.x); }
template <typename T>
// using T = int;
struct F {
int height, width;
vector<T> data;
explicit F(int h, int w) : height(h), width(w), data(h * w) {}
F() : F(1, 1) {}
inline bool safe(int y, int x) const {
return 0 <= y && y < height && 0 <= x && x < width;
}
inline bool safe(P p) const {
return 0 <= p.y && p.y < height && 0 <= p.x && p.x < width;
}
#if 1
void assert_safe(int y, int x) const {
if (!safe(y, x)) {
clog << "assertion failed: field=" << height << "x" << width
<< ": try=" << y << "," << x << endl;
assert(safe(y, x));
}
}
inline T &operator()(int y, int x) {
assert_safe(y, x);
return data[x + y * width];
}
inline T &operator()(P p) {
assert_safe(p.y, p. x);
return data[p.x + p.y * width];
}
inline T operator()(int y, int x) const {
assert_safe(y, x);
return data[x + y * width];
}
inline T operator()(P p) const {
assert_safe(p.y, p.x);
return data[p.x + p.y * width];
}
#else
inline T &operator()(int y, int x) { return data[x + y * width]; }
inline T &operator()(P p) { return data[p.x + p.y * width]; }
inline T operator()(int y, int x) const { return data[x + y * width]; }
inline T operator()(P p) const { return data[p.x + p.y * width]; }
#endif
inline T getA(int i) const { return data[i]; }
inline T &getAmut(int i) { return data[i]; }
inline void fill(T e) { std::fill(data.begin(), data.end(), e); }
inline void resize(int h, int w) {
height = h;
width = w;
data.resize(h * w);
}
void print(ostream &os, int setw_arg = 4) {
for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x)
os << setw(setw_arg) << operator()(y, x) << ' ';
os << '\n';
}
}
};
class CommandLine {
map<string, string> params;
void initializeInternal(int argc, char **argv) {
for (int i = 1; i < argc; ++i) {
if (argv[i][0] == '-') { // TODO: `=` 区切りにしたい
if (i + 1 < argc) {
params.emplace(argv[i], argv[i + 1]);
i += 1;
}
}
}
}
CommandLine() = default;
public:
static CommandLine &get() {
static CommandLine g;
return g;
}
static void initialize(int argc, char **argv) {
get().initializeInternal(argc, argv);
}
const string &str(const string &key) {
static const string empty_str;
auto it = params.find(key);
if (it == params.end()) {
return empty_str;
}
return it->second;
}
long long number(const string &key, long long default_value = 0) {
auto it = params.find(key);
if (it == params.end()) {
return default_value;
}
return atoi(it->second.c_str());
}
};
//
namespace appenv {
// 起動引数
int g_k_parameter = 4;
} // namespace appenv
// ----------------------------------------------------------------------------
// グリッドのサイズ
constexpr int N = 10;
// 操作回数最大
constexpr int T = 1000;
// オンラインクエリなら不要
// オフラインクエリなら実装する
struct PInput {
F<int> grid;
};
struct PAnswer {
string commands;
};
// ------------------------------------
class Judge {
public:
// オフラインクエリなら実装をそのまま使う
virtual const PInput &input() = 0;
virtual void output(const PAnswer &ans) = 0;
virtual int score() = 0;
};
//
class JudgeStdio : public Judge {
bool loaded_ = false;
PInput pi_;
int score_ = 0;
public:
const PInput &input() override {
if (loaded_)
return pi_;
int n, t;
scanner >> n >> t;
assert(n == N && t == T);
pi_.grid.resize(N, N);
repeat(y, N) {
repeat(x, N) {
int a;
scanner >> a;
pi_.grid(y, x) = a;
}
}
loaded_ = true;
return pi_;
}
void output(const PAnswer &ans) override {
for (char c : ans.commands) {
printer << c << "\n";
}
}
int score() override { return 0; }
};
// ----------------------------------------------------------------------------
struct Emulator {
F<int> grid_;
P current_pos_;
bool error_ = false;
int value_ = 0;
int apply_count_ = 0;
Emulator(const PInput &input) : grid_(input.grid), current_pos_(0, 0) {}
P getCurrentPosition() const { return current_pos_; }
bool hasError() const { return error_; }
int getValue() const { return value_; }
void applyCommand(char command) {
if (error_)
return;
if (apply_count_ >= T) {
error_ = true;
return;
}
switch (command) {
case 'U':
if (grid_.safe(current_pos_.y - 1, current_pos_.x)) {
current_pos_.y -= 1;
} else {
error_ = true;
}
break;
case 'D':
if (grid_.safe(current_pos_.y + 1, current_pos_.x)) {
current_pos_.y += 1;
} else {
error_ = true;
}
break;
case 'L':
if (grid_.safe(current_pos_.y, current_pos_.x - 1)) {
current_pos_.x -= 1;
} else {
error_ = true;
}
break;
case 'R':
if (grid_.safe(current_pos_.y, current_pos_.x + 1)) {
current_pos_.x += 1;
} else {
error_ = true;
}
break;
case 'W':
grid_(current_pos_) ^= value_;
break;
case 'C':
value_ ^= grid_(current_pos_);
break;
default:
error_ = true; // 不明なコマンド
}
++apply_count_;
}
};
string genereteCommandMoveTo(P curr, P target) {
string commands;
while (curr != target) {
if (curr.y < target.y) {
commands += 'D';
curr.y += 1;
} else if (curr.y > target.y) {
commands += 'U';
curr.y -= 1;
} else if (curr.x < target.x) {
commands += 'R';
curr.x += 1;
} else if (curr.x > target.x) {
commands += 'L';
curr.x -= 1;
}
}
return commands;
}
// ----------------------------------------------------------------------------
/*
基本方針
グリッドは忘れていい 実装が面倒なだけ
総和を最大化なので上の方のビットが立っていると嬉しい
すべての要素について一番上のビットが立っている状態にするのは簡単
→ 立っているものを選び、立っていないものにxorしていく
次の手がない。なぜなら、すべての要素で一番上のビットが立っているので、次にxorすると必ず一番上のビットが消滅する
→ No、手持ちの値も xor で編集されるので、なんかそれなりに錬成できる
*/
// 順序は固定されない、かつunique
void applyTo(Emulator &emulator, string &out_commands, const vector<P> &targets,
char apply_command) {
map<int, vector<int>> yx_map;
for (const P &target : targets) {
yx_map[target.y].push_back(target.x);
}
bool flip = false;
for (auto &pair : yx_map) {
sort(pair.second.begin(), pair.second.end());
if (flip) {
reverse(pair.second.begin(), pair.second.end());
}
flip = !flip; // 交互に反転
}
for (auto &pair : yx_map) {
const int y = pair.first;
for (const int x : pair.second) {
P target(y, x);
string move_commands =
genereteCommandMoveTo(emulator.getCurrentPosition(), target);
for (char command : move_commands) {
emulator.applyCommand(command);
}
emulator.applyCommand(apply_command);
out_commands += move_commands;
out_commands += apply_command;
}
}
}
// fi: 下からみて最初に立っているビットの位置
bool isValidClz(int value, int fi) {
if (value == 0)
return false; // 0は無効
int clz = countl_zero<uint32_t>(value);
int x = 31 - clz; // 0-indexed
return fi == x;
}
// (CurrentValue ^ res1 ^ res2 ^ ...) = 0001xxx..となるような組を探す
// TODO: 改善
vector<P> findBestXorCell(const F<int> &grid, int current_value, int fi,
const vector<P> &forbidden) {
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
P p(y, x);
if (isValidClz(current_value ^ grid(p), fi)) {
return {p};
}
}
}
upto(cnt, 2, 16, 1) {
repeat(t, 1000) {
vector<P> candidates;
int value = current_value;
repeat(i, cnt) {
int k = rand<int>(0, forbidden.size() - 1);
P p = forbidden[k];
candidates.push_back(p);
value ^= grid(p);
}
if (isValidClz(value, fi)) {
return candidates;
}
}
}
return {};
}
// (CurrentValue ^ cell) & mask = mask となるような場所をすべて探す
vector<P> findXorCells(const F<int> &grid, int current_value, int mask,
const vector<P> &forbidden) {
vector<P> result;
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
P p(y, x);
if (find(forbidden.begin(), forbidden.end(), p) != forbidden.end()) {
continue;
}
if (((current_value ^ grid(p)) & mask) == mask) {
result.push_back(p);
}
}
}
return result;
}
// 次のような列を作る
// ret[i]のセルをxorしていく; isValidClz(i)を満たす
// i は 19 downto 0 なので注意
pair<int, vector<vector<P>>> makeStrategy(const F<int> &grid,
const vector<P> &cells) {
vector<vector<P>> ret(20);
const int n = cells.size();
int curr_value = 0;
// 最初の1つめは1つだけ
for (const P &p : cells) {
if (isValidClz(grid(p), 19)) {
ret[19].push_back(p);
curr_value ^= grid(p);
break;
}
}
int min_ok = 19;
rrepeat(idx, 19) {
int bestn = n;
int bestbit = -1;
repeat(bit, 1 << n) {
int value = curr_value;
repeat(i, n) {
if (bit & (1 << i)) {
value ^= grid(cells[i]);
}
}
if (isValidClz(value, idx)) {
int m = bitset<32>(bit).count();
if (bestn > m) {
bestn = m;
bestbit = bit;
}
}
}
if (bestbit == -1) {
break;
}
{
repeat(i, n) {
if (bestbit & (1 << i)) {
ret[idx].push_back(cells[i]);
curr_value ^= grid(cells[i]);
}
}
}
min_ok = idx;
}
return {min_ok, ret};
}
// 戦略を最適化するはずだったもの
pair<vector<vector<P>>, vector<P>> solveStrategy(const F<int> &grid) {
vector<P> base_cells;
repeat(y, 3) {
repeat(x, 3) {
P p(y, x);
if (grid.safe(p)) {
base_cells.push_back(p);
}
}
}
// 3x3 が移動コストの都合上最適なので、探索する価値なし
vector<vector<P>> best_strategy;
vector<P> best_cells;
pair<int, int> best_score = {20, 0};
repeat(t, 2) {
shuffle(base_cells.begin(), base_cells.end(), randdev);
const int n = min(10, (int)base_cells.size());
vector<P> cells(n);
int xmin = N, xmax = 0, ymin = N, ymax = 0;
repeat(i, n) {
cells[i] = base_cells[i];
xmin = min(xmin, cells[i].x);
xmax = max(xmax, cells[i].x);
ymin = min(ymin, cells[i].y);
ymax = max(ymax, cells[i].y);
}
int area = (xmax - xmin + 1) * (ymax - ymin + 1);
auto strategy = makeStrategy(grid, cells);
pair<int, int> score = {strategy.first, area};
if (score < best_score) {
best_strategy = move(strategy.second);
best_cells = move(cells);
best_score = score;
}
}
return {best_strategy, best_cells};
}
template <typename OutputStream>
void printTable(OutputStream &out, const F<int> &grid) {
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
rrepeat(i, 20) { out << !!(grid(y, x) & (1 << i)); }
out << ' ';
}
out << '\n';
}
}
string int2bin(int n) {
string result;
for (int i = 19; i >= 0; --i) {
result += !!(n & (1 << i)) + '0';
}
return result;
}
// オフラインクエリ用（使うのはPInput）
class SolverOfflineSample {
const PInput &input_;
SolverOfflineSample(const PInput &input) : input_(input) {}
PAnswer solve() {
string output_commands;
Emulator emulator(input_);
auto [strategy, forbidden_cells] = solveStrategy(emulator.grid_);
int mask = 0;
rrepeat(i, 20) {
mask |= 1 << i;
int printer_mask = 1 << i;
// vector<P> targets =
// findBestXorCell(emulator.grid_, emulator.getValue(), i,
// forbidden_cells);
// if (targets.empty()) {
// break;
// }
vector<P> targets = strategy[i];
if (targets.empty()) {
break;
}
applyTo(emulator, output_commands, targets, 'C');
vector<P> xor_cells = findXorCells(emulator.grid_, emulator.getValue(),
mask, forbidden_cells);
LOG << "mask = " << int2bin(mask)
<< " printer_mask = " << int2bin(printer_mask)
<< " value = " << int2bin(emulator.getValue())
<< " xor_cells.len = " << xor_cells.size() << endl;
if (xor_cells.empty()) {
continue;
}
applyTo(emulator, output_commands, xor_cells, 'W');
if (emulator.hasError()) {
LOG << "error occurred commandlens = " << output_commands.size();
break;
}
printTable(clog, emulator.grid_);
}
PAnswer ans;
LOG << "commands.len = " << output_commands.size();
if (output_commands.size() > T) {
output_commands.resize(T);
}
ans.commands = output_commands;
return ans;
}
public:
const static void solve(Judge &judge) {
const PInput &input = judge.input();
SolverOfflineSample solver(input);
judge.output(solver.solve());
}
};
//
void appMain() {
JudgeStdio judge;
SolverOfflineSample::solve(judge);
// clog << "score = " << judge.score() << endl;
}
//
#define LOAD_CONSTANT_FROM_ARGS(konst, arg) \
{ \
const string &v = CommandLine::get().str(arg); \
if (!v.empty()) \
konst = atoi(v.c_str()); \
}
int main(int argc, char **argv) {
using namespace appenv;
CommandLine::initialize(argc, argv);
LOAD_CONSTANT_FROM_ARGS(g_k_parameter, "--a-parater");
appMain();
return 0;
}