結果

問題 No.5022 XOR Printer
コンテスト
ユーザー yimiya（いみや）
提出日時 2025-07-26 14:43:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,406 bytes
コンパイル時間 3,988 ms
コンパイル使用メモリ 310,600 KB
実行使用メモリ 7,716 KB
スコア 4,447,588,841
最終ジャッジ日時 2025-07-26 14:43:40
合計ジャッジ時間 5,287 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MAX_OP = 1000;
ll N, T;
vector<vector<ll>> grid;
ll cnt = 0;
ll x = 0, y = 0;
ll s = 0;

bool move(ll ex, ll ey) {
    ll dx = ex - x;
    ll dy = ey - y;
    if (cnt + abs(dx) + abs(dy) > MAX_OP) return false;
    while (dx != 0) {
        cout << (dx > 0 ? "R" : "L") << "\n";
        x += (dx > 0 ? 1 : -1);
        dx += (dx > 0 ? -1 : 1);
        cnt++;
    }
    while (dy != 0) {
        cout << (dy > 0 ? "D" : "U") << "\n";
        y += (dy > 0 ? 1 : -1);
        dy += (dy > 0 ? -1 : 1);
        cnt++;
    }
    return true;
}

bool copy() {
    if (cnt + 1 > MAX_OP) return false;
    s ^= grid[y][x];
    cout << "C\n";
    cnt++;
    return true;
}

bool write() {
    if (cnt + 1 > MAX_OP) return false;
    ll old_val = grid[y][x];
    ll new_val = old_val ^ s;
    if (new_val > old_val) {
        grid[y][x] = new_val;
        cout << "W\n";
        cnt++;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> T;
    grid.resize(N, vector<ll>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> grid[i][j];

    // 方針：高ビットを持つマスにsをコピーして、低ビットを持つマスにXORして書き換える
    vector<tuple<int, int, int>> cells; // {bitcount, y, x}
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cells.emplace_back(__builtin_popcountll(grid[i][j]), i, j);

    // 高ビットから順に処理
    sort(cells.rbegin(), cells.rend());

    for (auto [bitc, sy, sx] : cells) {
        if (!move(sx, sy)) break;
        if (!copy()) break;

        // 近いマスを探索してXORした方が良くなるものを書き換える
        vector<tuple<ll, int, int>> delta_list;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                ll before = grid[i][j];
                ll after = before ^ s;
                if (after > before)
                    delta_list.emplace_back(after - before, i, j);
            }
        }

        // スコアの増加が大きい順に処理
        sort(delta_list.rbegin(), delta_list.rend());
        for (auto [delta, ty, tx] : delta_list) {
            if (!move(tx, ty)) goto END;
            if (!write()) goto END;
        }
    }

END:
    return 0;
}
0