結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 Ang1077
|
| 提出日時 | 2025-07-26 13:25:20 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,486 bytes |
| コンパイル時間 | 3,425 ms |
| コンパイル使用メモリ | 292,476 KB |
| 実行使用メモリ | 19,016 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2025-07-26 13:25:31 |
| 合計ジャッジ時間 | 10,344 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 1 -- * 49 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, T;
if (!(cin >> N >> T)) return 0;
vector<vector<uint32_t>> A(N, vector<uint32_t>(N));
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> A[i][j];
// 0-indexed state
int r = 0, c = 0;
uint32_t s = 0;
vector<char> ops;
auto move_to = [&](int tr, int tc) {
while (r < tr) { ops.push_back('D'); ++r; }
while (r > tr) { ops.push_back('U'); --r; }
while (c < tc) { ops.push_back('R'); ++c; }
while (c > tc) { ops.push_back('L'); --c; }
};
// Precompute all-pairs Manhattan distances on the grid (flattened indices 0..N*N-1)
const int M = N * N;
auto idx = [&](int rr, int cc){ return rr * N + cc; };
vector<array<int,2>> rc(M);
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) rc[idx(i,j)] = {i,j};
vector<vector<int>> dist(M, vector<int>(M, 0));
for (int a = 0; a < M; ++a) {
for (int b = 0; b < M; ++b) {
dist[a][b] = abs(rc[a][0] - rc[b][0]) + abs(rc[a][1] - rc[b][1]);
}
}
int used = 0;
while (used < T) {
int rem = T - used;
long long best_delta = 0;
int best_cost = 0;
int cur = idx(r, c);
int plan_w = -1;
int plan_p1 = -1;
int plan_p2 = -1;
int plan_p3 = -1;
int plan_k = 0; // 0/1/2/3 copies
// 0C
for (int w = 0; w < M; ++w) {
int cost = dist[cur][w] + 1; // move + W
if (cost > rem) continue;
auto [wr, wc] = rc[w];
uint32_t new_val = (A[wr][wc] ^ s);
long long delta = (long long)new_val - (long long)A[wr][wc];
if (delta > best_delta) {
best_delta = delta;
best_cost = cost;
plan_k = 0;
plan_w = w;
plan_p1 = plan_p2 = plan_p3 = -1;
}
}
// 1C
for (int p1 = 0; p1 < M; ++p1) {
int cost_to_p1 = dist[cur][p1] + 1; // move + C
if (cost_to_p1 + 1 > rem) continue; // need W
uint32_t s1 = s ^ A[ rc[p1][0] ][ rc[p1][1] ];
for (int w = 0; w < M; ++w) {
int cost = cost_to_p1 + dist[p1][w] + 1; // + move + W
if (cost > rem) continue;
auto [wr, wc] = rc[w];
uint32_t new_val = (A[wr][wc] ^ s1);
long long delta = (long long)new_val - (long long)A[wr][wc];
if (delta > best_delta) {
best_delta = delta;
best_cost = cost;
plan_k = 1;
plan_p1 = p1;
plan_w = w;
plan_p2 = plan_p3 = -1;
}
}
}
// 2C
if (rem >= 3) {
for (int p1 = 0; p1 < M; ++p1) {
int cost0 = dist[cur][p1] + 1; // move + C
if (cost0 + 2 > rem) continue; // need C + W
uint32_t s1 = s ^ A[ rc[p1][0] ][ rc[p1][1] ];
for (int p2 = 0; p2 < M; ++p2) {
int cost1 = cost0 + dist[p1][p2] + 1; // move + C
if (cost1 + 1 > rem) continue; // need W
uint32_t s2 = s1 ^ A[ rc[p2][0] ][ rc[p2][1] ];
for (int w = 0; w < M; ++w) {
int cost = cost1 + dist[p2][w] + 1; // move + W
if (cost > rem) continue;
auto [wr, wc] = rc[w];
uint32_t new_val = (A[wr][wc] ^ s2);
long long delta = (long long)new_val - (long long)A[wr][wc];
if (delta > best_delta) {
best_delta = delta;
best_cost = cost;
plan_k = 2;
plan_p1 = p1;
plan_p2 = p2;
plan_w = w;
plan_p3 = -1;
}
}
}
}
}
// 3C
if (rem >= 4) {
for (int p1 = 0; p1 < M; ++p1) {
int cost0 = dist[cur][p1] + 1; // move + C
if (cost0 + 3 > rem) continue; // need C + C + W
uint32_t s1 = s ^ A[ rc[p1][0] ][ rc[p1][1] ];
for (int p2 = 0; p2 < M; ++p2) {
int cost1 = cost0 + dist[p1][p2] + 1; // move + C
if (cost1 + 2 > rem) continue; // need C + W
uint32_t s2 = s1 ^ A[ rc[p2][0] ][ rc[p2][1] ];
for (int p3 = 0; p3 < M; ++p3) {
int cost2 = cost1 + dist[p2][p3] + 1; // move + C
if (cost2 + 1 > rem) continue; // need W
uint32_t s3 = s2 ^ A[ rc[p3][0] ][ rc[p3][1] ];
for (int w = 0; w < M; ++w) {
int cost = cost2 + dist[p3][w] + 1; // move + W
if (cost > rem) continue;
auto [wr, wc] = rc[w];
uint32_t new_val = (A[wr][wc] ^ s3);
long long delta = (long long)new_val - (long long)A[wr][wc];
if (delta > best_delta) {
best_delta = delta;
best_cost = cost;
plan_k = 3;
plan_p1 = p1;
plan_p2 = p2;
plan_p3 = p3;
plan_w = w;
}
}
}
}
}
}
if (best_delta <= 0 || plan_w < 0) break;
// execute
if (plan_k == 0) {
auto [wr, wc] = rc[plan_w];
move_to(wr, wc);
ops.push_back('W');
A[wr][wc] ^= s;
} else if (plan_k == 1) {
auto [p1r, p1c] = rc[plan_p1];
move_to(p1r, p1c);
ops.push_back('C');
s ^= A[p1r][p1c];
auto [wr, wc] = rc[plan_w];
move_to(wr, wc);
ops.push_back('W');
A[wr][wc] ^= s;
} else if (plan_k == 2) {
auto [p1r, p1c] = rc[plan_p1];
move_to(p1r, p1c);
ops.push_back('C');
s ^= A[p1r][p1c];
auto [p2r, p2c] = rc[plan_p2];
move_to(p2r, p2c);
ops.push_back('C');
s ^= A[p2r][p2c];
auto [wr, wc] = rc[plan_w];
move_to(wr, wc);
ops.push_back('W');
A[wr][wc] ^= s;
} else { // plan_k == 3
auto [p1r, p1c] = rc[plan_p1];
move_to(p1r, p1c);
ops.push_back('C');
s ^= A[p1r][p1c];
auto [p2r, p2c] = rc[plan_p2];
move_to(p2r, p2c);
ops.push_back('C');
s ^= A[p2r][p2c];
auto [p3r, p3c] = rc[plan_p3];
move_to(p3r, p3c);
ops.push_back('C');
s ^= A[p3r][p3c];
auto [wr, wc] = rc[plan_w];
move_to(wr, wc);
ops.push_back('W');
A[wr][wc] ^= s;
}
used += best_cost;
}
for (char ch : ops) cout << ch << '\n';
return 0;
}