結果

問題 No.5022 XOR Printer
ユーザー bird01
提出日時 2025-07-26 14:50:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,127 bytes
コンパイル時間 3,132 ms
コンパイル使用メモリ 287,556 KB
実行使用メモリ 7,716 KB
スコア 4,575,659,115
最終ジャッジ日時 2025-07-26 14:50:55
合計ジャッジ時間 5,802 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 1.ベースライン,何もしない
// 2.最適なsを求め,全セルをフリップ→?
// 3.最大桁を1にする
// 4.2桁目も1にする→壊れている
// 5.2桁目も1にする

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

#define rep(i,a,b) for (int i = (a); i < (b); i++)

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

  int n, t;
  cin >> n >> t;
  vector<vector<int>> A(n, vector<int>(n));
  rep(i, 0, n) rep(j, 0, n) cin >> A[i][j];

  vector<char> ops;
  int cx = 0, cy = 0;
  int s = 0;

  // 移動ヘルパー: (cx,cy) から (tx,ty) へ
  auto moveTo = [&](int tx, int ty) {
    while (cx < tx) { ops.push_back('D'); ++cx; }
    while (cx > tx) { ops.push_back('U'); --cx; }
    while (cy < ty) { ops.push_back('R'); ++cy; }
    while (cy > ty) { ops.push_back('L'); --cy; }
  };

  // --- Phase1: 最上位ビット bit1 を 1 にする ---
  int bit1 = -1;
  rep(i, 0, n) rep(j, 0, n) if (A[i][j] > 0) {
    int b = 31 - __builtin_clz(A[i][j]);
    bit1 = max(bit1, b);
  }
  while (bit1 >= 0) {
    bool ok = false;
    rep(i, 0, n) rep(j, 0, n) {
      if ((A[i][j] >> bit1) & 1) { ok = true; break; }
    }
    if (ok) break;
    --bit1;
  }
  if (bit1 < 0) return 0;

  int bi = -1, bj = -1, bd = INT_MAX;
  rep(i, 0, n) rep(j, 0, n) {
    if ((A[i][j] >> bit1) & 1) {
      int d = abs(i - cx) + abs(j - cy);
      if (d < bd) { bd = d; bi = i; bj = j; }
    }
  }
  moveTo(bi, bj);
  ops.push_back('C');
  s ^= A[bi][bj];  // コピーで s 更新

  moveTo(0, 0);
  rep(i, 0, n) {
    if (i % 2 == 0) {
      rep(j, 0, n) {
        moveTo(i, j);
        if (!((A[i][j] >> bit1) & 1)) {
          ops.push_back('W');
          A[i][j] ^= s;
        }
      }
    } else {
      for (int j = n - 1; j >= 0; --j) {
        moveTo(i, j);
        if (!((A[i][j] >> bit1) & 1)) {
          ops.push_back('W');
          A[i][j] ^= s;
        }
      }
    }
  }

  // --- Phase2: bit1 を保持しつつ bit2 を 1 にする ---
  int bit2 = bit1 - 1;
  while (bit2 >= 0) {
    bool ok = false;
    rep(i, 0, n) rep(j, 0, n) {
      if ((A[i][j] >> bit2) & 1) { ok = true; break; }
    }
    if (ok) break;
    --bit2;
  }
  if (bit2 < 0) {
    rep(idx, 0, ops.size()) cout << ops[idx] << '\n';
    return 0;
  }

  // 今回の目標 s: s ^ A[i][j] の結果が bit2 を含むケース
  bi = -1; bj = -1; bd = INT_MAX;
  rep(i, 0, n) rep(j, 0, n) {
    int cand = s ^ A[i][j];
    if ((cand >> bit2) & 1) {
      int d = abs(i - cx) + abs(j - cy);
      if (d < bd) { bd = d; bi = i; bj = j; }
    }
  }
  moveTo(bi, bj);
  ops.push_back('C');
  s ^= A[bi][bj];  // コピーで bit2 を取り込む

  moveTo(0, 0);
  rep(i, 0, n) {
    if (i % 2 == 0) {
      rep(j, 0, n) {
        moveTo(i, j);
        if (!((A[i][j] >> bit2) & 1)) {
          ops.push_back('W');
          A[i][j] ^= s;
        }
      }
    } else {
      for (int j = n - 1; j >= 0; --j) {
        moveTo(i, j);
        if (!((A[i][j] >> bit2) & 1)) {
          ops.push_back('W');
          A[i][j] ^= s;
        }
      }
    }
  }

  rep(idx, 0, ops.size()) cout << ops[idx] << '\n';
  return 0;
}
0