結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 wanui
|
| 提出日時 | 2025-07-26 15:58:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,397 bytes |
| コンパイル時間 | 2,121 ms |
| コンパイル使用メモリ | 217,148 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 312,855,977 |
| 最終ジャッジ日時 | 2025-07-26 15:59:49 |
| 合計ジャッジ時間 | 106,724 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 TLE * 47 |
コンパイルメッセージ
main.cpp: In function ‘std::pair<board_t, std::vector<signed char> > rulebased(board_t, std::vector<signed char>)’:
main.cpp:229:111: warning: narrowing conversion of ‘(((std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type)((distance_table[bd.board_t::player][z] + distance_table[z][o]) * 100)) + (marathon::engine.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()() % 100))’ from ‘std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
229 | bestpair = min(bestpair, {(distance_table[bd.player][z] + distance_table[z][o]) * 100 + marathon::engine() % 100, {z, o}});
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>
// clang-format off
#ifdef ONLINE_JUDGE
const int LOCAL = 1;
#else
const int LOCAL = 1;
#endif
using namespace std;
#define debug1(a) {if(LOCAL){cerr<<#a<<":"<<a<<endl; }}
#define debug2(a,b) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; }}
#define debug3(a,b,c) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; }}
#define debug4(a,b,c,d) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; }}
#define debug5(a,b,c,d,e) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<" "<<#e<<":"<<e<<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 int_to_bits(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 (cost > T - bd.total_cost) 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) {
int TS = 940;
// XORの性質を考えると「上の桁から順に 0→1 にする」のがよい
auto bd = init_bd;
auto ops = init_ops;
auto op_move = [&](int u) {
bd.total_cost += distance_table[bd.player][u];
bd.player = u;
ops.push_back(u);
assert(bd.total_cost <= T);
};
auto op_write = [&]() {
bd.total_cost += 1;
bd.tbl[bd.player] = bd.x ^ bd.tbl[bd.player];
ops.push_back(WRITE);
assert(bd.total_cost <= T);
};
auto op_copy = [&]() {
bd.total_cost += 1;
bd.x = bd.x ^ bd.tbl[bd.player];
ops.push_back(COPY);
assert(bd.total_cost <= T);
};
bitset<N2> ignored = 0;
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++) {
if (ignored[u]) continue;
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) * 100 + marathon::engine() % 100, u}, bestmv);
}
}
if (bestmv.first > TS - bd.total_cost) break;
{
int u = bestmv.second;
op_move(u);
op_copy();
}
}
// debug3(bit, bd.x, bd.player);
vector<int> goals;
vector<int> nongoals;
for (int u = 0; u < N2; u++) {
if (ignored[u]) continue;
if ((bd.x ^ bd.tbl[u]) > bd.tbl[u]) {
goals.push_back(u);
} else {
nongoals.push_back(u);
}
}
{
pair<int, pii> bestpair = {inf, {inf, inf}};
while (goals.size()) {
// debug1(goals.size());
// TODO TSPをちゃんと解く
pii min_g = {inf, inf};
for (auto g : goals) {
min_g = min(min_g, {(distance_table[bd.player][g] + 1) * 100 + marathon::engine() % 100, g});
}
if (min_g.first / 100 > TS - bd.total_cost) break;
{
int g = min_g.second;
op_move(g);
op_write();
marathon::vecremove_first(goals, g);
}
}
if (goals.size() >= 1) break;
if (bit > 0 && bit < 19) {
// 1110と、1111を1個ずつ確保
int nbit = bit - 1;
vector<int> zero;
vector<int> one;
for (auto g : nongoals) {
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[bd.player][z] + distance_table[z][o]) * 100 + marathon::engine() % 100, {z, o}});
}
}
if (bestpair.first >= inf) break;
int s = bestpair.second.first;
int t = bestpair.second.second;
// debug2(bit, int_to_bits(bd.x));
if (distance_table[bd.player][s] + distance_table[s][t] + 4 > TS - bd.total_cost) break;
op_move(s);
op_write();
op_copy();
op_write();
op_move(t);
op_copy();
// debug3(bit, int_to_bits(bd.x), bd.total_cost);
ignored[s] = 1;
}
}
}
// debug2("rulebased end", bd.total_cost);
return {bd, ops};
}
pair<int, vector<int8_t>> 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);
int score = 0;
for (int u = 0; u < N2; u++) {
score += bd.tbl[u];
}
return {score, 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);
}
}
}
}
pair<int, vector<int8_t>> best;
best.first = -1;
for (int loop = 0; marathon::now() < 1950; loop++) {
int s;
vector<int8_t> ops;
tie(s, ops) = solve();
best = max(best, {s, ops});
if (loop % 100 == 0) debug3(loop, s, best.first);
}
output(best.second);
return 0;
}