結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 K2
|
| 提出日時 | 2025-07-26 15:16:27 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,984 ms / 2,000 ms |
| コード長 | 6,754 bytes |
| コンパイル時間 | 3,289 ms |
| コンパイル使用メモリ | 303,004 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 4,790,449,772 |
| 最終ジャッジ日時 | 2025-07-26 15:18:15 |
| 合計ジャッジ時間 | 106,686 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
struct Timer {
using Clock = chrono::high_resolution_clock;
chrono::time_point<Clock> st{Clock::now()};
double elapsed() const {
return chrono::duration<double>(Clock::now() - st).count();
}
};
constexpr int N = 10;
constexpr int T = 1000;
constexpr int choose = 6;
constexpr int seed = 123456789;
constexpr double TL = 1.98;
tuple<int64_t, string, vector<vector<uint32_t>>> run(const vector<char>& out,
vector<vector<uint32_t>>& board) {
size_t x = 0, y = 0;
uint32_t s = 0;
size_t step = 0;
for (char op : out) {
switch (op) {
case 'U':
if (x == 0) {
return {0, "Move out of board at step " + to_string(step), board};
}
--x;
break;
case 'D':
if (x + 1 >= static_cast<size_t>(N)) {
return {0, "Move out of board at step " + to_string(step), board};
}
++x;
break;
case 'L':
if (y == 0) {
return {0, "Move out of board at step " + to_string(step), board};
}
--y;
break;
case 'R':
if (y + 1 >= static_cast<size_t>(N)) {
return {0, "Move out of board at step " + to_string(step), board};
}
++y;
break;
case 'W':
board[x][y] ^= s;
break;
case 'C':
s ^= board[x][y];
break;
default:
return {0, "Invalid operation", board};
}
++step;
}
uint64_t sum = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
sum += board[i][j];
}
}
return {static_cast<int64_t>(sum), "", board};
}
int main() {
int n_in, t_in;
if (!(cin >> n_in >> t_in)) return 0;
vector<vector<uint32_t>> A(N, vector<uint32_t>(N, 0));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> A[i][j];
}
}
Timer timer;
mt19937 rng(seed);
uniform_int_distribution<int> dist(0, N*N - 1);
int best_score = -1;
int iter = 0;
vector<int> best_combination, best_candidate_vals;
while (timer.elapsed() < TL) {
vector<int> combination, candidate_vals;
while (combination.size() < choose) {
int idx = dist(rng);
if (find(combination.begin(), combination.end(), idx) == combination.end()) {
combination.emplace_back(idx);
}
}
candidate_vals.emplace_back(0);
for (int i = 0; i < choose; ++i) {
candidate_vals.emplace_back(A[combination[i] / N][combination[i] % N] ^ candidate_vals.back());
}
int score = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
uint32_t val = 0;
for (int v : candidate_vals) {
val = max(val, A[i][j] ^ v);
}
score += val;
}
}
if (score > best_score) {
best_score = score;
best_combination = combination;
best_candidate_vals = candidate_vals;
}
iter++;
}
// for (int idx : best_combination) {
// cerr << idx << ' ' << A[idx / N][idx % N] << endl;
// }
// cerr << "Best score: " << best_score << endl;
// cerr << "Iterations: " << iter << endl;
vector<vector<int>> result(N, vector(N, -1));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (find(best_combination.begin(), best_combination.end(), i * N + j) != best_combination.end()) {
continue;
}
int val = -1;
int idx = -1;
for (int k = 0; k < choose + 1; ++k) {
int candidate_val = A[i][j] ^ best_candidate_vals[k];
if (candidate_val > val) {
val = candidate_val;
idx = k;
}
}
result[i][j] = idx;
}
}
int score = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (result[i][j] == -1) {
score += A[i][j];
} else {
score += A[i][j] ^ best_candidate_vals[result[i][j]];
}
}
}
cerr << "Final score: " << score << endl;
vector<char> output;
output.reserve(1000);
vector A_ = A;
int s = 0;
int curr_x = 0, curr_y = 0; // 現在位置を追跡
for (int i = 0; i < choose + 1; ++i) {
assert(s == best_candidate_vals[i]);
// cerr << "s: " << s << endl;
// cerr << "predicted: " << best_candidate_vals[i] << endl;
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
int y = (j % 2 == 0) ? k : N - 1 - k; // jが偶数ならk, 奇数ならN-1-k
if (result[j][y] == i) {
output.emplace_back('W');
A_[j][y] ^= s;
}
if (k != N-1) {
output.emplace_back(j % 2 ? 'L' : 'R');
curr_y += (j % 2 ? -1 : 1);
}
}
if (j != N-1) {
output.emplace_back('D');
curr_x++;
}
}
if (i == choose) break;
// 目標位置への移動
int target_x = best_combination[i] / N;
int target_y = best_combination[i] % N;
// X方向の移動
while (curr_x > target_x) {
output.emplace_back('U');
curr_x--;
}
// Y方向の移動
while (curr_y < target_y) {
output.emplace_back('R');
curr_y++;
}
output.emplace_back('C');
s ^= A_[target_x][target_y];
while (curr_y > 0) {
output.emplace_back('L');
curr_y--;
}
while (curr_x > 0) {
output.emplace_back('U');
curr_x--;
}
}
int res_score = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
res_score += A_[i][j];
cerr << A_[i][j] << ' ';
}
cerr << endl;
}
cerr << "Result score: " << res_score << endl;
auto res = run(output, A);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cerr << get<2>(res)[i][j] << ' ';
}
cerr << endl;
}
cerr << "Run result: " << get<0>(res) << ", " << get<1>(res) << endl;
for (char c : output) {
cout << c << endl;
}
}