結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 wanui
|
| 提出日時 | 2025-07-26 14:52:04 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,404 bytes |
| コンパイル時間 | 2,610 ms |
| コンパイル使用メモリ | 212,644 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 4,532,405,558 |
| 最終ジャッジ日時 | 2025-07-26 14:52:09 |
| 合計ジャッジ時間 | 4,687 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 44 WA * 6 |
ソースコード
#include <bits/stdc++.h>
// clang-format off
using namespace std;
#define debug1(a) { cerr<<#a<<":"<<a<<endl; }
#define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; }
#define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; }
#define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; }
// clang-format on
const double CLOCK_RATIO = 1000;
using pii = pair<int, int>;
namespace marathon {
std::mt19937 engine(0);
clock_t start_time;
double now() {
return CLOCK_RATIO * (clock() - start_time) / CLOCKS_PER_SEC;
}
void marathon_init() {
start_time = clock();
std::random_device seed_gen;
engine.seed(seed_gen());
}
template <typename T>
void vecremove_first(std::vector<T> &vec, T elem) {
// elemに一致する最初の要素を削除
vec.erase(std::find(vec.begin(), vec.end(), elem));
}
}; // namespace marathon
const int inf = 1e9;
const int N = 10;
const int T = 1000;
const int N2 = 100;
int INIT_TBL[N2];
int distance_table[N2][N2];
const int8_t COPY = -1;
const int8_t WRITE = -2;
string to_bit(int x) {
string res;
for (int b = 19; b >= 0; b--) {
if ((x >> b) & 1) {
res.push_back('1');
} else {
res.push_back('0');
}
}
return res;
}
void output(vector<int8_t> ops) {
int player = 0;
for (auto op : ops) {
if (op == COPY) {
cout << "C" << endl;
} else if (op == WRITE) {
cout << "W" << endl;
} else {
pii p = {player / N, player % N};
pii g = {op / N, op % N};
while (p != g) {
if (p.first < g.first) {
cout << "D" << endl;
p.first++;
} else if (p.first > g.first) {
cout << "U" << endl;
p.first--;
} else if (p.second < g.second) {
cout << "R" << endl;
p.second++;
} else if (p.second > g.second) {
cout << "L" << endl;
p.second--;
} else {
assert(0);
}
}
player = op;
}
}
}
struct board_t {
int total_cost;
int tbl[N2];
int x;
int player;
};
pair<board_t, vector<int8_t>> greedy(board_t init_bd, vector<int8_t> init_ops) {
vector<int8_t> ops = init_ops;
auto bd = init_bd;
while (true) {
pair<int, pii> bestop = {-1, {-1, -1}};
for (int s = 0; s < N2; s++) {
for (int t = 0; t < N2; t++) {
int cost = distance_table[bd.player][s] + distance_table[s][t] + 2;
if (cost > 15) continue;
if (bd.total_cost + cost > T) continue;
int y = bd.x ^ bd.tbl[s];
int oldval = bd.tbl[t];
int newval = bd.tbl[t] ^ y;
if (newval <= oldval) continue;
bestop = max(bestop, {newval - oldval, {s, t}});
}
}
if (bestop.first < 0) break;
{
int8_t s = bestop.second.first;
int8_t t = bestop.second.second;
ops.push_back(s);
ops.push_back(COPY);
ops.push_back(t);
ops.push_back(WRITE);
bd.x = bd.x ^ bd.tbl[s];
bd.tbl[t] = bd.x ^ bd.tbl[t];
bd.total_cost += distance_table[bd.player][s] + distance_table[s][t] + 2;
bd.player = t;
}
}
return {bd, ops};
}
pair<board_t, vector<int8_t>> rulebased(board_t init_bd, vector<int8_t> init_ops) {
// XORの性質を考えると「上の桁から順に 0→1 にする」のがよい
auto bd = init_bd;
auto ops = init_ops;
for (int bit = 19; bit >= 0; bit--) {
bool must_change = false;
{
if (((bd.x >> bit) & 1) == 0) must_change = true;
for (int b = bit + 1; b <= 19; b++) {
if (((bd.x >> b) & 1) > 0) must_change = true;
}
}
if (must_change) {
pii bestmv = {inf, -1};
for (int u = 0; u < N2; u++) {
int y = bd.x ^ bd.tbl[u];
if (((y >> bit) & 1) == 0) continue;
bool ok = true;
for (int b = bit + 1; b <= 19; b++) {
if ((y >> b) & 1) ok = false;
}
if (ok) {
bestmv = min(pii{distance_table[bd.player][u] + 1, u}, bestmv);
}
}
if (bestmv.first + bd.total_cost > T) break;
{
int u = bestmv.second;
bd.total_cost += distance_table[bd.player][u] + 1;
bd.x = bd.x ^ bd.tbl[u];
bd.player = u;
ops.push_back(u);
ops.push_back(COPY);
}
}
// debug3(bit, bd.x, bd.player);
vector<int> goals;
for (int u = 0; u < N2; u++) {
if ((bd.x ^ bd.tbl[u]) > bd.tbl[u]) {
goals.push_back(u);
}
}
{
pair<int, pii> bestpair = {inf, {inf, inf}};
if (bit > 0 && bit < 19) {
// 1100と、1101を1個ずつ確保
int nbit = bit - 1;
vector<int> zero;
vector<int> one;
for (auto g : goals) {
if ((bd.tbl[g] >> nbit) & 1) {
one.push_back(g);
} else {
zero.push_back(g);
}
}
// debug2(one.size(), zero.size());
for (auto z : zero) {
for (auto o : one) {
bestpair = min(bestpair, {distance_table[z][o], {z, o}});
}
}
}
while (goals.size()) {
// debug1(goals.size());
// TODO TSPをちゃんと解く
pii min_g = {inf, inf};
for (auto g : goals) {
if (g == bestpair.second.first || g == bestpair.second.second) continue;
min_g = min(min_g, {distance_table[bd.player][g] + 1, g});
}
if (min_g.first + bd.total_cost > T) break;
{
int g = min_g.second;
bd.total_cost += distance_table[bd.player][g] + 1;
bd.player = g;
bd.tbl[g] = bd.x ^ bd.tbl[g];
ops.push_back(g);
ops.push_back(WRITE);
marathon::vecremove_first(goals, g);
}
}
if (bestpair.first < inf) {
int s = bestpair.second.first;
int t = bestpair.second.second;
// debug2(s, t);
debug2(bit, to_bit(bd.x));
if (distance_table[bd.player][s] + distance_table[s][t] + 3 > T) break;
ops.push_back(s);
bd.player = s;
ops.push_back(WRITE);
bd.tbl[s] = bd.x ^ bd.tbl[s];
ops.push_back(COPY);
bd.x = bd.x ^ bd.tbl[s];
ops.push_back(t);
bd.player = t;
ops.push_back(COPY);
bd.x = bd.x ^ bd.tbl[t];
debug2(bit, to_bit(bd.x))
}
else {
if (goals.size() >= 1) break;
}
}
}
return {bd, ops};
}
void solve() {
vector<int8_t> ops;
board_t bd;
bd.player = 0;
bd.x = 0;
bd.total_cost = 0;
for (int u = 0; u < N2; u++) {
bd.tbl[u] = INIT_TBL[u];
}
tie(bd, ops) = rulebased(bd, ops);
tie(bd, ops) = greedy(bd, ops);
output(ops);
}
int main() {
marathon::marathon_init();
int n, t;
cin >> n >> t;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
cin >> INIT_TBL[r * N + c];
}
}
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
distance_table[r * N + c][i * N + j] = abs(r - i) + abs(c - j);
}
}
}
}
solve();
return 0;
}