結果

問題 No.5022 XOR Printer
コンテスト
ユーザー 👑 wanui
提出日時 2025-07-26 13:48:55
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 3,182 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,202 ms
コンパイル使用メモリ 203,196 KB
実行使用メモリ 7,716 KB
スコア 4,903,579,484
最終ジャッジ日時 2025-07-26 13:48:59
合計ジャッジ時間 4,427 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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
using pii = pair<int, int>;
const int N = 10;
const int T = 1000;
const int N2 = 100;
int INIT_TBL[N2];
int distance_table[N2][N2];

void output(vector<int8_t> ops) {
    int player = 0;
    for (auto op : ops) {
        if (op == -1) {
            cout << "C" << endl;
        } else if (op == -2) {
            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;
        }
    }
}
void solve() {
    vector<int8_t> ops;

    vector<int> tbl(N2);
    for (int u = 0; u < N2; u++) {
        tbl[u] = INIT_TBL[u];
    }
    int total_cost = 0;
    int player = 0;
    int x = 0;
    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[player][s] + distance_table[s][t] + 2;
                if (cost > 15) continue;
                if (total_cost + cost > T) continue;
                int y = x ^ tbl[s];
                int oldval = tbl[t];
                int newval = 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(-1);
            ops.push_back(t);
            ops.push_back(-2);

            x = x ^ tbl[s];
            tbl[t] = x ^ tbl[t];
            total_cost += distance_table[player][s] + distance_table[s][t] + 2;
            player = t;
        }
    }
    output(ops);
}
int main() {
    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;
}
0