結果

問題 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}});
      |                                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#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;
}
0