#1107855 (C++17) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: many bear
• 提出日時: 2025-07-26 14:09:36
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 7,079 bytes
• コンパイル時間: 3,888 ms
• コンパイル使用メモリ: 257,888 KB
• 実行使用メモリ: 7,716 KB
• スコア: 2,659,818,750
• 最終ジャッジ日時: 2025-07-26 14:09:43
• 合計ジャッジ時間: 6,287 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

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

コンパイルメッセージ

main.cpp:3:9: warning: #pragma once in main file
    3 | #pragma once
      |         ^~~~
main.cpp:58:9: warning: #pragma once in main file
   58 | #pragma once
      |         ^~~~
main.cpp:135:9: warning: #pragma once in main file
  135 | #pragma once
      |         ^~~~
main.cpp:241:9: warning: #pragma once in main file
  241 | #pragma once
      |         ^~~~
main.cpp:245:9: warning: #pragma once in main file
  245 | #pragma once
      |         ^~~~
main.cpp: In member function ‘void State::apply(int)’:
main.cpp:236:24: warning: narrowing conversion of ‘data’ from ‘int’ to ‘char’ [-Wnarrowing]
  236 |     actions.push_back({data});
      |                        ^~~~

ソースコード

// Template for competitive programming (atcoder heuristic contest)
// this template is only for marathon problems. not for long term use.
#pragma once
#ifdef ONLINE_JUDGE
#define NDEBUG
#include <atcoder/all>
#endif
#include <bits/stdc++.h>
using namespace atcoder;

using namespace std;
int INF = 1e9;
using P = pair<int, int>;
#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reprev(i, n) for (int i = (n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define for_(i, a, b) for (int i = (a); i < (b); i++)
#define all(v) v.begin(), v.end()
template <typename T>
inline bool chmin(T &a, const T &b)
{
  bool c = a > b;
  if (c)
    a = b;
  return c;
}
template <typename T>
inline bool chmax(T &a, const T &b)
{
  bool c = a < b;
  if (c)
    a = b;
  return c;
}
template <typename T>
inline T ceil(T a, T b) { return (a + (b - 1)) / b; }
template <typename T>
using vc = vector<T>;
template <class T>
istream &operator>>(istream &i, vc<T> &v)
{
  rep(j, (int)size(v)) i >> v[j];
  return i;
}
template <class T>
ostream &operator<<(ostream &o, const vc<T> &v)
{
  rep(j, (int)size(v))
  {
    if (j)
      o << " ";
    o << v[j];
  }
  o << endl;
  return o;
}
#pragma once


// ref:https://qiita.com/sorachandu/items/041169d34b9f9b99bcf7#timer-%E6%99%82%E9%96%93%E8%A8%88%E6%B8%AC%E7%94%A8class
class Timer
{
  chrono::system_clock::time_point start;

public:
  Timer() : start(chrono::system_clock::now()) {}

  double count()
  {
    chrono::duration<double> Time_ = chrono::system_clock::now() - start;
    return Time_.count();
  }

  bool is_under(double x)
  {
    return (this->count()) < x;
  }
};
Timer timer;

// ref :https://atcoder.jp/contests/ahc048/submissions/66624955
class Random
{
public:
  Random() : state_(3141592653589793238ULL) {}

  double RandomDouble(double a, double b)
  {
    Update();
    const double r = state_ * kScale_;
    return a + (b - a) * r;
  }

  int RandomInt(int a, int b)
  {
    return static_cast<int>(RandomDouble(a, b));
  }

  int RandomIntInclusive(int a, int b)
  {
    return RandomInt(a, b + 1);
  }

private:
  uint64_t state_;

  // 2^(-64)
  static constexpr double kScale_ = 1.0 / 18446744073709551616.0;

  void Update()
  {
    // xorshift
    state_ ^= state_ >> 13;
    state_ ^= state_ << 7;
    state_ ^= state_ >> 17;
  }
};

#ifdef _GLIBCXX_DEBUG
class OStreamRedirect
{
  std::ostream &os;
  std::streambuf *old_buf;

public:
  OStreamRedirect(std::ostream &os_, std::ostream &new_stream)
      : os(os_), old_buf(os_.rdbuf(new_stream.rdbuf())) {}
  ~OStreamRedirect()
  {
    os.rdbuf(old_buf);
  }
};
#endif
#pragma once

extern int N, T;
extern vc<vc<int>> A;
struct Action
{
  // TODO: implement here for individual problem
  //  int data;
  char action_type; // UDLR, C, W.
  friend ostream &operator<<(ostream &o, const Action &a)
  {
    cout << a.action_type << endl;
    return o;
  }
};

class State
{
public:
  vc<Action> actions;
  // only for beam search
  int hash = 0;

  int calc_score() const
  {
    int score = 0;
    vc<vc<int>> board = A;
    {
      int S = 0;
      int i = 0;
      int j = 0;
      for (const auto &action : actions)
      {
        if (action.action_type == 'U')
        {
          if (i == 0)
            assert(false);
          i--;
        }
        else if (action.action_type == 'D')
        {
          if (i == N - 1)
            assert(false);
          i++;
        }
        else if (action.action_type == 'L')
        {
          if (j == 0)
            assert(false);
          j--;
        }
        else if (action.action_type == 'R')
        {
          if (j == N - 1)
            assert(false);
          j++;
        }
        else if (action.action_type == 'C')
        {
          S = board[i][j];
        }
        else if (action.action_type == 'W')
        {
          board[i][j] ^= S;
        }
        else
        {
          assert(false);
        }
      }
    }
    rep(i, N)
    {
      rep(j, N)
      {
        score += board[i][j];
      }
    }
    return score;
  }
  // TODO: Implement output format for each problem
  friend ostream &operator<<(ostream &o, const State &state)
  {
    // Example: output number of actions, then each action
    // o << state.actions.size() << endl;
    rep(i, state.actions.size())
    {
      o << state.actions[i];
    }
    return o;
  }
  friend bool operator<(const State &a, const State &b)
  {
    return a.calc_score() < b.calc_score();
  }
  friend bool operator>(const State &a, const State &b)
  {
    return a.calc_score() > b.calc_score();
  }
  void apply(int data)
  {
    actions.push_back({data});
    // Update  if necessary
  }
};

#pragma once



#pragma once




extern int N, T;
extern vc<vc<int>> A;
class Greedy
{
public:
  State solve_all()
  {
    rep(i, 1)
    {
      State state;
      solved_state = solve_partial(state);
    }
    return solved_state;
  }

  State solve_partial(State &state, int seed = 0 /*If you are going to use beam search, don't make this method deterministic.*/)
  {
    collect_maximum(state);
    return state;
  }

  const State &get_solved_state() const
  {
    return solved_state;
  }

private:
  State solved_state;

  // �O���b�h A �̍ő�l�̈ʒu�܂ňړ�����
  void collect_maximum(State &state)
  {
    int max_val = -1, mx = 0, my = 0;
    rep(i, N) rep(j, N) if (A[i][j] > max_val)
    {
      max_val = A[i][j];
      mx = i;
      my = j;
    }
    int ci = 0, cj = 0;
    // ����
    while (ci < mx)
    {
      state.actions.push_back({'D'});
      ci++;
    }
    // ���
    while (ci > mx)
    {
      state.actions.push_back({'U'});
      ci--;
    }
    // �E��
    while (cj < my)
    {
      state.actions.push_back({'R'});
      cj++;
    }
    // ����
    while (cj > my)
    {
      state.actions.push_back({'L'});
      cj--;
    }
  }
};
// #include "simulated_annealing.cpp"
// #include "beam_search.cpp"
void solve()
{

#ifdef _GLIBCXX_DEBUG
  ofstream coutdbg("output.txt");
  OStreamRedirect redirect_cout(cout, coutdbg);
#endif

  timer = Timer();
  // greedy
  Greedy greedy;
  State state = greedy.solve_all();

  // Simulated Annealing
  // Greedy greedy;
  // SimulatedAnnealing sa(greedy);
  // State state = sa.simulate();
  //

  //  Beam Search
  //  Greedy greedy;
  //  BeamSearch beam_search(greedy, 10);
  //  State state = beam_search.search();

#ifdef _GLIBCXX_DEBUG
  ofstream coutgreedy("greedy_output.txt");
  coutgreedy << state;
  flush(coutgreedy);
#endif
  // cout << state.actions.size() << endl;
  // TODO: check the output format of the problem.
  cout << state;
  flush(cout);
}



// TODO:Store input data here in global variables
// int N;
// vc<int> A;
// you have to use extern to refer these variables;
int N, T;
vc<vc<int>> A;
void input()
{
  cin >> N >> T;
  A.assign(N, vc<int>(N));
  cin >> A;
}
int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  // ref:https://rsk0315.hatenablog.com/entry/2020/05/09/170315
  input();
  solve();
  return 0;
}