#1108083 (C++23) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: hidehic0
• 提出日時: 2025-07-26 16:43:23
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 273 ms / 2,000 ms
• コード長: 3,937 bytes
• コンパイル時間: 3,182 ms
• コンパイル使用メモリ: 302,848 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,673,781,481
• 最終ジャッジ日時: 2025-07-26 16:43:44
• 合計ジャッジ時間: 17,830 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
other	AC * 50

ソースコード

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

const long long INF = 1LL << 40;
int N, T;
vector<vector<int>> A;

// Function to read a single integer
int ii() {
  int x;
  cin >> x;
  return x;
}

// Function to read a line of integers into a vector
vector<int> il(int add_num = 0) {
  string s;
  getline(cin, s);
  stringstream ss(s);
  vector<int> res;
  int x;
  while (ss >> x) {
    res.push_back(x + add_num);
  }
  return res;
}

// Function to read multiple lines of input
vector<vector<int>> li(int n) {
  vector<vector<int>> res(n);
  for (int i = 0; i < n; ++i) {
    res[i] = il();
  }
  return res;
}

// Calculate score for a given list of moves
long long getscore(const vector<pair<int, int>> &L) {
  long long c = 0;
  vector<vector<int>> NA = A; // Deep copy
  long long t = 0;

  for (const auto &[i, k] : L) {
    c ^= NA[i][k];
    t += (i + k + 2) * 2;
    t += 140;

    if (t > T) {
      return -INF;
    }

    for (int a = 0; a < N; ++a) {
      for (int b = 0; b < N; ++b) {
        if (i != a || k != b) {
          NA[a][b] = max(NA[a][b], static_cast<int>(NA[a][b] ^ c));
          t += 1;
        }
      }
    }
  }

  if (t > T) {
    return -INF;
  }

  long long score = 0;
  for (int i = 0; i < N; ++i) {
    score += accumulate(NA[i].begin(), NA[i].end(), 0LL);
  }
  return score;
}

// Generate output sequence based on moves
vector<string> get_output(const vector<pair<int, int>> &L) {
  long long c = 0;
  vector<vector<int>> NA = A; // Deep copy
  vector<string> res;

  for (const auto &[i, k] : L) {
    c ^= NA[i][k];
    // Move down
    for (int j = 0; j < i; ++j)
      res.push_back("D");
    // Move right
    for (int j = 0; j < k; ++j)
      res.push_back("R");
    // Choose cell
    res.push_back("C");
    // Move left
    for (int j = 0; j < k; ++j)
      res.push_back("L");
    // Move up
    for (int j = 0; j < i; ++j)
      res.push_back("U");

    bool f = false;
    for (int x = 0; x < N; ++x) {
      int y = f ? N - 1 : 0;
      int dy = f ? -1 : 1;

      while (0 <= y && y < N) {
        if ((x != i || y != k) && NA[x][y] < (NA[x][y] ^ c)) {
          res.push_back("W");
          NA[x][y] ^= c;
        }
        if ((f && y != 0) || (!f && y != N - 1)) {
          res.push_back(f ? "L" : "R");
        }
        y += dy;
      }

      if (x != N - 1) {
        res.push_back("D");
      }
      f = !f;
    }

    // Move up to top
    for (int j = 0; j < N - 1; ++j)
      res.push_back("U");
  }

  return res;
}

int main() {
  // Read input
  cin >> N >> T;
  cin.ignore(); // Clear newline after N T
  A = li(N);

  vector<pair<int, int>> l;
  long long sc = -INF;

  // Try single move
  for (int i = 0; i < N; ++i) {
    for (int k = 0; k < N; ++k) {
      long long nc = getscore({{i, k}});
      if (sc < nc) {
        l = {{i, k}};
        sc = nc;
      }
    }
  }

  // Try two moves
  for (int ai = 0; ai < N; ++ai) {
    for (int ak = 0; ak < N; ++ak) {
      for (int bi = 0; bi < N; ++bi) {
        for (int bk = 0; bk < N; ++bk) {
          long long nc = getscore({{ai, ak}, {bi, bk}});
          if (sc < nc) {
            l = {{ai, ak}, {bi, bk}};
            sc = nc;
          }
        }
      }
    }
  }

  // Random search
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  for (int _ = 0; _ < 200000; ++_) {
    int m = uniform_int_distribution<int>(3, 4)(rng);
    vector<pair<int, int>> nl;
    set<pair<int, int>> used;

    for (int j = 0; j < m; ++j) {
      int x, y;
      do {
        x = uniform_int_distribution<int>(0, N - 1)(rng);
        y = uniform_int_distribution<int>(0, N - 1)(rng);
      } while (used.count({x, y}));
      nl.emplace_back(x, y);
      used.emplace(x, y);
    }

    long long nc = getscore(nl);
    if (sc < nc) {
      l = nl;
      sc = nc;
    }
  }

  // Output result
  auto res = get_output(l);
  for (const auto &s : res) {
    cout << s << '\n';
  }

  return 0;
}