結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 SnowBeenDiding
|
| 提出日時 | 2025-07-26 14:56:34 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 4,908 bytes |
| コンパイル時間 | 2,921 ms |
| コンパイル使用メモリ | 291,196 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 5,166,492,876 |
| 最終ジャッジ日時 | 2025-07-26 14:56:40 |
| 合計ジャッジ時間 | 4,902 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
In lambda function,
inlined from ‘solve(std::vector<std::vector<int> >, int, int)::<lambda(int, int)>’ at main.cpp:38:13,
inlined from ‘std::pair<int, std::__cxx11::basic_string<char> > solve(std::vector<std::vector<int> >, int, int)’ at main.cpp:97:14:
main.cpp:13:19: warning: ‘one_i’ may be used uninitialized [-Wmaybe-uninitialized]
13 | while (ni > i) {
| ~~~^~~
main.cpp: In function ‘std::pair<int, std::__cxx11::basic_string<char> > solve(std::vector<std::vector<int> >, int, int)’:
main.cpp:75:13: note: ‘one_i’ was declared here
75 | int one_i, one_j, one_dist = 1e9;
| ^~~~~
In lambda function,
inlined from ‘solve(std::vector<std::vector<int> >, int, int)::<lambda(int, int)>’ at main.cpp:38:13,
inlined from ‘std::pair<int, std::__cxx11::basic_string<char> > solve(std::vector<std::vector<int> >, int, int)’ at main.cpp:97:14:
main.cpp:21:19: warning: ‘one_j’ may be used uninitialized [-Wmaybe-uninitialized]
21 | while (nj > j) {
| ~~~^~~
main.cpp: In function ‘std::pair<int, std::__cxx11::basic_string<char> > solve(std::vector<std::vector<int> >, int, int)’:
main.cpp:75:20: note: ‘one_j’ was declared here
75 | int one_i, one_j, one_dist = 1e9;
| ^~~~~
In lambda function,
inlined from ‘solve(std::vector<std::vector<int> >, int, int)::<lambda(int, int)>’ at main.cpp:33:13,
inlined from ‘std::pair<int, std::__cxx11::basic_string<char> > solve(std::vector<std::vector<int> >, int, int)’ at main.cpp:99:13:
main.cpp:13:19: warning: ‘zero_i’ may be used uninitialized [-Wmaybe-uninitialized]
13 | while (ni > i) {
| ~~~^~~
main.cpp: In function ‘std::pair<int, std::__cxx11::basic_string<char> > solve(std::vector<std::vector<int> >, int, int)’:
main.cpp:76:13: note: ‘zero_i’ was declared here
76 | int zero_i, zero_j, zero_d
ソースコード
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace std;
typedef long long ll;
pair<int, string> solve(vector<vector<int>> a, int n, int t) {
auto b = a;
int hand = 0;
int ni = 0, nj = 0;
string ans;
auto move = [&](int i, int j) {
while (ni > i) {
ans += 'U';
ni--;
}
while (ni < i) {
ans += 'D';
ni++;
}
while (nj > j) {
ans += 'L';
nj--;
}
while (nj < j) {
ans += 'R';
nj++;
}
ni = i;
nj = j;
};
auto copy = [&](int i, int j) {
move(i, j);
ans += 'C';
hand ^= a[i][j];
};
auto write = [&](int i, int j) {
move(i, j);
ans += 'W';
a[i][j] ^= hand;
};
auto update = [&](int i, int j) {
if ((a[i][j] ^ hand) > a[i][j]) {
write(i, j);
}
};
rep(i, 0, n) rep(j, 0, n) {
if ((hand == 0) && ((a[i][j] >> 19) & 1)) {
copy(i, j);
}
}
rep(i, 0, n) {
if (i % 2 == 0) {
for (int j = 0; j < n; j++) {
if (!((a[i][j] >> 19) & 1)) {
write(i, j);
}
}
} else {
for (int j = n - 1; j >= 0; j--) {
if (!((a[i][j] >> 19) & 1)) {
write(i, j);
}
}
}
}
for (int d = 18; d >= 0; d--) {
vector<vector<int>> exclusion(n, vector<int>(n));
int mask = (1 << 20) - (1 << (d + 2));
rep(i, 0, n) rep(j, 0, n) {
if ((a[i][j] & mask) != mask) {
exclusion[i][j] = 1;
}
}
int one_i, one_j, one_dist = 1e9;
int zero_i, zero_j, zero_dist = 1e9;
rep(i, 0, n) rep(j, 0, n) {
if (exclusion[i][j]) continue;
int dist = abs(i - ni) + abs(j - nj);
if ((a[i][j] >> d) & 1) {
if (dist < one_dist) {
one_dist = dist;
one_i = i;
one_j = j;
}
} else {
if (dist < zero_dist) {
zero_dist = dist;
zero_i = i;
zero_j = j;
}
}
}
if (one_dist == 1e9 || zero_dist == 1e9) {
break;
}
write(one_i, one_j);
copy(one_i, one_j);
copy(zero_i, zero_j);
if (d % 2 == 1) {
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
for (int j = 0; j < n; j++) {
update(i, j);
}
} else {
for (int j = n - 1; j >= 0; j--) {
update(i, j);
}
}
}
} else {
for (int i = n - 1; i >= 0; i--) {
if (i % 2 == 0) {
for (int j = n - 1; j >= 0; j--) {
update(i, j);
}
} else {
for (int j = 0; j < n; j++) {
update(i, j);
}
}
}
}
}
ans = ans.substr(0, t);
auto calc_score = [&](vector<vector<int>> a, int n, string ans) {
int ni = 0, nj = 0;
int hand = 0;
for (char c : ans) {
if (c == 'U')
ni--;
else if (c == 'D')
ni++;
else if (c == 'L')
nj--;
else if (c == 'R')
nj++;
else if (c == 'C')
hand ^= a[ni][nj];
else if (c == 'W')
a[ni][nj] ^= hand;
}
int score = 0;
rep(i, 0, n) rep(j, 0, n) { score += a[i][j]; }
return score;
};
return {calc_score(b, n, ans), ans};
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, t;
cin >> n >> t;
vector<vector<int>> a(n, vector<int>(n));
rep(i, 0, n) rep(j, 0, n) cin >> a[i][j];
auto result = solve(a, n, t);
rep(i, 0, n) rep(j, i + 1, n) swap(a[i][j], a[j][i]);
auto result_transposed = solve(a, n, t);
cerr << "Score: " << result.first << " vs " << result_transposed.first
<< '\n';
if (result.first > result_transposed.first) {
for (auto c : result.second) {
cout << c << '\n';
}
} else {
for (auto c : result_transposed.second) {
if (c == 'R')
c = 'D';
else if (c == 'D')
c = 'R';
else if (c == 'L')
c = 'U';
else if (c == 'U')
c = 'L';
cout << c << '\n';
}
}
}