結果
問題 |
No.5022 XOR Printer
|
ユーザー |
|
提出日時 | 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; }