結果

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

ソースコード

diff # 

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

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

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

typedef pair<int,int> pii;

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;

  // マンハッタン距離
  auto dist = [&](int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
  };

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

  // 最大ビットを取得
  int maxBit = 0;
  rep(i, 0, n) rep(j, 0, n) if (A[i][j] > 0) {
    int b = 31 - __builtin_clz(A[i][j]);
    maxBit = max(maxBit, b);
  }

  // 各ビット (大きい方から) を処理
  rep(order, 0, maxBit+1) {
    if (ops.size() >= T) break;
    int bit = maxBit - order;

    // 1) セル選択: i=0 (order==0) は単一、それ以降は_PAIR_
    vector<pii> single;
    vector<pair<pii,pii>> pairs;

    // 単一候補: bit が立ち、上位ビットすべて0
    rep(i, 0, n) rep(j, 0, n) {
      int v = A[i][j];
      if (((v >> bit) & 1) == 1) {
        bool ok = true;
        for (int b2 = bit+1; b2 <= maxBit; b2++) if ((v >> b2) & 1) { ok = false; break; }
        if (ok) single.emplace_back(i,j);
      }
    }

    // ペア候補: XOR が条件を満たす
    rep(i1, 0, n) rep(j1, 0, n) rep(i2, 0, n) rep(j2, 0, n) {
      if (order == 0) break;
      if (i1 * n + j1 >= i2 * n + j2) continue;
      int v = A[i1][j1] ^ A[i2][j2];
      if (((v >> bit) & 1) == 1) {
        bool ok = true;
        for (int b2 = bit+1; b2 <= maxBit; b2++) if ((v >> b2) & 1) { ok = false; break; }
        if (ok) pairs.emplace_back(pii(i1,j1), pii(i2,j2));
      }
    }

    // 最適セル群の選択
    vector<pii> sel;
    int bestD = INT_MAX;
    if (order == 0) {
      for (auto &p : single) {
        int d = dist(cx,cy,p.first,p.second);
        if (d < bestD) {
          bestD = d;
          sel = {p};
        }
      }
    } else {
      for (auto &pr : pairs) {
        auto p1 = pr.first, p2 = pr.second;
        int d1 = dist(cx,cy,p1.first,p1.second) + dist(p1.first,p1.second,p2.first,p2.second);
        int d2 = dist(cx,cy,p2.first,p2.second) + dist(p2.first,p2.second,p1.first,p1.second);
        int d = min(d1, d2);
        if (d < bestD) {
          bestD = d;
          if (d1 <= d2) sel = {p1,p2}; else sel = {p2,p1};
        }
      }
    }
    if (sel.empty()) continue;

    // 2) 選択したセルを順番に訪問しコピー
    set<int> skip;
    rep(k, 0, sel.size()) {
      int x = sel[k].first, y = sel[k].second;
      moveTo(x, y);
      if (ops.size() >= T) break;
      ops.push_back('C');
      s ^= A[x][y];
      skip.insert(x*n+y);
    }
    if (ops.size() >= T) break;

    // 3) 全セル蛇行走査して書き込み
    rep(i, 0, n) {
      if (i % 2 == 0) rep(j, 0, n) {
        moveTo(i,j);
        if (ops.size() >= T) break;
        int idx = i*n + j;
        if (skip.count(idx)) continue;
        int nxt = A[i][j] ^ s;
        if (nxt > A[i][j]) {
          ops.push_back('W');
          A[i][j] = nxt;
        }
      } else for (int j = n-1; j >= 0; --j) {
        moveTo(i,j);
        if (ops.size() >= T) break;
        int idx = i*n + j;
        if (skip.count(idx)) continue;
        int nxt = A[i][j] ^ s;
        if (nxt > A[i][j]) {
          ops.push_back('W');
          A[i][j] = nxt;
        }
      }
      if (ops.size() >= T) break;
    }
    if (ops.size() >= T) break;

    // 4) s をリセット: 選択セルを再訪問しコピー
    rep(k, 0, sel.size()) {
      int x = sel[k].first, y = sel[k].second;
      moveTo(x, y);
      if (ops.size() >= T) break;
      ops.push_back('C');
      s ^= A[x][y];
    }
    if (ops.size() >= T) break;

    // 5) (0,0) に戻す
    moveTo(0,0);
    if (ops.size() >= T) break;
  }

  // 出力
  rep(i, 0, ops.size()) cout << ops[i] << '\n';
  return 0;
}
0