結果

問題 No.5022 XOR Printer
ユーザー many bear
提出日時 2025-07-26 15:06:49
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 8,593 bytes
コンパイル時間 3,885 ms
コンパイル使用メモリ 260,132 KB
実行使用メモリ 7,716 KB
スコア 4,980,269,835
最終ジャッジ日時 2025-07-26 15:06:56
合計ジャッジ時間 6,124 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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:213:9: warning: #pragma once in main file
  213 | #pragma once
      |         ^~~~
main.cpp:217:9: warning: #pragma once in main file
  217 | #pragma once
      |         ^~~~

ソースコード

diff # 

// 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;
  vc<vc<int>> board = A;
  int i = 0, j = 0; // current position
  int S = 0;

  int calc_score() const
  {
    int score = 0;
    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(char data)
  {
    if (actions.size() >= T)
      return; // Do not apply if we reached the turn limit
    actions.push_back({data});
    // Update  if necessary
    if (data == 'U')
      i--;
    else if (data == 'D')
      i++;
    else if (data == 'L')
      j--;
    else if (data == 'R')
      j++;
    else if (data == 'C')
      S ^= board[i][j]; // Collect the current cell value
    else if (data == 'W')
      board[i][j] ^= S;
  }
};

#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.*/)
  {
    find_and_replace(state);
    return state;
  }

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

private:
  State solved_state;

  // �O���b�h A �̍ő�l�̈ʒu�܂ňړ����ăR�s�[
  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;
    }
    move_to(state, mx, my);
    state.apply('C');
  }

  // �S�}�X��0�ɂ���i�ő�l�Z���ȊO�j�����ʒu�ɖ߂�
  void make_all_zero(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;
    }
    rep(i, N) rep(j, N) if (!(i == mx && j == my))
    {
      move_to(state, i, j);
      state.apply('C');
      state.apply('W');
    }
    move_to(state, mx, my);
  }

  // ���݈ʒu (state.i, state.j) ���� (target_i, target_j) �ֈړ�
  void move_to(State &state, int target_i, int target_j)
  {
    while (state.i < target_i && state.actions.size() < T)
    {
      state.apply('D');
    }

    while (state.i > target_i && state.actions.size() < T)
    {
      state.apply('U');
    }
    while (state.j < target_j && state.actions.size() < T)
    {
      state.apply('R');
    }
    while (state.j > target_j && state.actions.size() < T)
    {
      state.apply('L');
    }
  }

  // �ŏ��Ƀr�b�g�d�����ŏ��̃y�A�����A�ȍ~�� s �ƍŏ��d���̃Z����R��X�V
  void find_and_replace(State &state)
  {

    // �ŏ��d���y�A (bi,bj) �� (ci,cj) ��T��
    int best = 0, bi = 0, bj = 0, ci = 0, cj = 0;
    rep(i1, N) rep(j1, N) rep(i2, N) rep(j2, N)
    {
      if (i1 == i2 && j1 == j2)
        continue; // �����Z���͏��O
      int ov = state.board[i1][j1] ^ state.board[i2][j2];
      if (ov > best)
      {
        best = ov;
        bi = i1;
        bj = j1;
        ci = i2;
        cj = j2;
      }
    }
    if (state.board[bi][bj] > state.board[ci][cj])
    {
      swap(bi, ci);
      swap(bj, cj);
    }

    move_to(state, bi, bj);
    state.apply('C');
    move_to(state, ci, cj);
    state.apply('W');

    // �^�[�������܂ŌJ��Ԃ�
    while ((int)state.actions.size() < T)
    {
      int b2 = 0, ti = 0, tj = 0;
      rep(i1, N) rep(j1, N)
      {
        if (i1 == bi && j1 == bj)
          continue; // �����Z���͏��O
        int ov = state.S ^ state.board[i1][j1];
        if (ov > b2)
        {
          b2 = ov;
          ti = i1;
          tj = j1;
        }
      }
      move_to(state, ti, tj);
      state.apply('W');
      state.apply('C');
    }
  }
};
// #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;
}
0