結果
問題 |
No.5022 XOR Printer
|
ユーザー |
|
提出日時 | 2025-07-26 14:28:39 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 3,391 bytes |
コンパイル時間 | 3,730 ms |
コンパイル使用メモリ | 286,928 KB |
実行使用メモリ | 7,716 KB |
スコア | 4,721,287,485 |
最終ジャッジ日時 | 2025-07-26 14:28:46 |
合計ジャッジ時間 | 5,571 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include <bits/stdc++.h> using namespace std; // #include <atcoder/all> // using namespace atcoder; // #include<boost/multiprecision/cpp_int.hpp> // using bint = boost::multiprecision::cpp_int; random_device seed_gen; mt19937_64 rnd(seed_gen()); template <typename T> bool chmax(T& A, T B) { if (A < B) { A = B; return true; } return false; } template <typename T> bool chmin(T& A, T B) { if (A > B) { A = B; return true; } return false; } #define rep(i, m, n) for (int i = (m); i < (n); i++) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() using ll = long long; using pint = pair<ll, ll>; template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; #define PI 3.14159265358979323846264338327950288419716939937510 void bns(ll x, int p = 60) { for (int i = p - 1; i >= 0; i--) { cerr << (x >> i & 1LL); } cerr << endl; } int n, t; vector<vector<int>> a; vector<int> di = {-1, 1, 0, 0}; vector<int> dj = {0, 0, -1, 1}; string chars = "UDLR"; string op = ""; void input() { cin >> n >> t; a.assign(n, vector<int>(n)); rep (i, 0, n) rep (j, 0, n) cin >> a[i][j]; } void initAns() { // int i = 0, j = 0; // int s = 0; // rep (ti, 0, t) { // if (op.size() > t - 4) break; // vector<int> d = {0, 1, 2, 3}; // shuffle(all(d), rnd); // rep (k, 0, 4) { // int ni = i + di[d[k]], nj = j + dj[d[k]]; // if (ni >= 0 && ni < n && nj >= 0 && nj < n) { // op += chars[d[k]]; // i = ni, j = nj; // if ((a[i][j] ^ s) > a[i][j]) { // op += "W"; // a[i][j] ^= s; // } // uniform_int_distribution<int> dist_f(0, 1); // if (dist_f(rnd)) { // op += "C"; // s ^= a[i][j]; // } // break; // } // } // } pint pos = {0, 0}; int s = 0; op += "C"; s = a[0][0]; auto delta = [&](int i, int j) { return (a[i][j] ^ s) - a[i][j]; }; while (op.size() < t) { pint target; int delta_max = -1e9; rep (i, 0, n) rep (j, 0, n) { if (chmax(delta_max, delta(i, j))) { target = {i, j}; } } auto update = [&](int i, int j) { if (delta(i, j) > 0 && op.size() < t) { op += "W"; a[i][j] ^= s; } }; auto [i, j] = pos; auto [ni, nj] = target; while (i > ni && op.size() < t) { op += "U"; i--; update(i, j); } while (i < ni && op.size() < t) { op += "D"; i++; update(i, j); } while (j > nj && op.size() < t) { op += "L"; j--; update(i, j); } while (j < nj && op.size() < t) { op += "R"; j++; update(i, j); } if (op.size() < t) { op += "C"; s ^= a[i][j]; pos = {i, j}; } } } void output() { rep (ti, 0, op.size()) cout << op[ti] << endl; } void solve() { input(); initAns(); output(); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); solve(); return 0; }