結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 yt142857
|
| 提出日時 | 2025-07-26 15:31:23 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,306 bytes |
| コンパイル時間 | 3,558 ms |
| コンパイル使用メモリ | 303,124 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2025-07-26 15:33:01 |
| 合計ジャッジ時間 | 97,823 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 50 |
ソースコード
/*
import copy
import time
start_time = time.time()
def change(num):
re = []
for i in range(19,-1,-1):
if 2**i <= num:
num -= 2**i
re.append(1)
else:
re.append(0)
re.reverse()
return re
def go(s,g):
if s[0] < g[0]:
for i in range(g[0]-s[0]):
ans.append('D')
else:
for i in range(s[0]-g[0]):
ans.append('U')
if s[1] < g[1]:
for i in range(g[1]-s[1]):
ans.append('R')
else:
for i in range(s[1]-g[1]):
ans.append('L')
n,t = map(int,input().split())
al = []
ans = []
al_two = []
now_num = 0
for i in range(n):
s = [int(_) for _ in input().split()]
al.append(s)
other_s = []
for j in range(n):
other_s.append(change(s[j]))
al_two.append(other_s)
score = 0
for i in range(n):
for j in range(n):
score += al[i][j]
turn = 0
f_al = copy.deepcopy(al)
f_al_two = copy.deepcopy(al_two)
f_now_num = 0
f_score = score
max_score = 0
finaly_ans = 0
road = [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 9), (1, 8), (1, 7), (1, 6), (1, 5), (1, 4), (1, 3), (1, 2), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (3, 9), (3, 8), (3, 7), (3, 6), (3, 5), (3, 4), (3, 3), (3, 2), (3, 1), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (5, 9), (5, 8), (5, 7), (5, 6), (5, 5), (5, 4), (5, 3), (5, 2), (5, 1), (5, 0), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 8), (6, 9), (7, 9), (7, 8), (7, 7), (7, 6), (7, 5), (7, 4), (7, 3), (7, 2), (7, 1), (7, 0), (8, 0), (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7), (8, 8), (8, 9), (9, 9), (9, 8), (9, 7), (9, 6), (9, 5), (9, 4), (9, 3), (9, 2), (9, 1), (9, 0)]
import random
while (time.time()-start_time)*1000 <= 1800:
...
print(max_score)
for i in finaly_ans:
print(i)
*/
// C++ translation with identical behavior:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// turn and time measurement
auto start_time = chrono::steady_clock::now();
// Convert number to 20-bit binary (LSB first)
vector<int> change(int num) {
vector<int> re(20);
for (int i = 0; i < 20; i++) {
re[i] = (num >> i) & 1;
}
return re;
}
// Append moves from s to g into ans (but do NOT update turn here)
void go(const pair<int,int>& s, const pair<int,int>& g, vector<char>& ans) {
if (s.first < g.first) {
for (int i = 0; i < g.first - s.first; i++) ans.push_back('D');
} else {
for (int i = 0; i < s.first - g.first; i++) ans.push_back('U');
}
if (s.second < g.second) {
for (int i = 0; i < g.second - s.second; i++) ans.push_back('R');
} else {
for (int i = 0; i < s.second - g.second; i++) ans.push_back('L');
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, t;
cin >> n >> t;
vector<vector<int>> al(n, vector<int>(n));
vector<vector<vector<int>>> al_two(n, vector<vector<int>>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> al[i][j];
}
for (int j = 0; j < n; j++) {
al_two[i][j] = change(al[i][j]);
}
}
ll score = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
score += al[i][j];
// save initial state
auto f_al = al;
auto f_al_two = al_two;
ll f_score = score;
ll max_score = 0;
vector<char> final_ans;
// generate road: snake path through 10x10
vector<pair<int,int>> road;
for(int i = 0; i < 10; i++){
if(i % 2 == 0){
for(int j = 0; j < 10; j++) road.emplace_back(i,j);
} else {
for(int j = 9; j >= 0; j--) road.emplace_back(i,j);
}
}
// random engine
mt19937_64 rng(random_device{}());
uniform_real_distribution<double> uni(0.0,1.0);
// main hill-climb loop until 1800 ms
while (chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start_time).count() <= 1800) {
vector<char> ans;
al = f_al;
al_two = f_al_two;
int now_num = 0;
ll cur_score = f_score;
ll turn = 0;
for (int i = 16; i < 20; i++) {
pair<int,int> best_node = {-1,-1};
int best_node_num = numeric_limits<int>::max();
// find best_node
for (int j = 0; j < n; j++) {
for (int l = 0; l < n; l++) {
auto bits = change(now_num ^ al[j][l]);
if (bits[i] == 1 && al[j][l] < best_node_num) {
best_node = {j,l};
best_node_num = al[j][l];
}
}
}
// condition uses (i+j-2)*2+1 as in Python
if (turn + (best_node.first + best_node.second - 2) * 2 + 1 <= t) {
// go to best_node, do 'C', return to (0,0)
go({0,0}, best_node, ans);
ans.push_back('C');
now_num ^= al[best_node.first][best_node.second];
go(best_node, {0,0}, ans);
turn += (best_node.first + best_node.second) * 2 + 1;
// then traverse road
pair<int,int> now_node = {0,0};
for (auto &k : road) {
int j = k.first, l = k.second;
ll dist = llabs(now_node.first - j) + llabs(now_node.second - l);
if (turn + dist > t) break;
// decide to flip or maybe random
int new_val = al[j][l] ^ now_num;
if (new_val > al[j][l]) {
go(now_node, k, ans);
turn += dist;
now_node = k;
if (turn + 1 <= t) {
turn++;
ans.push_back('W');
cur_score += new_val - al[j][l];
al[j][l] = new_val;
al_two[j][l] = change(al[j][l]);
}
} else {
double p = pow((19.0 - i) / 10.0, 3);
if (uni(rng) < p) {
go(now_node, k, ans);
turn += dist;
now_node = k;
if (turn + 1 <= t) {
turn++;
ans.push_back('W');
cur_score += new_val - al[j][l];
al[j][l] = new_val;
al_two[j][l] = change(al[j][l]);
}
}
}
}
// return to origin if possible
ll back = now_node.first + now_node.second;
if (turn + back <= t) {
turn += back;
go(now_node, {0,0}, ans);
}
}
}
if (cur_score > max_score) {
max_score = cur_score;
final_ans = ans;
}
}
// output
cout << max_score << "\n";
for (char c : final_ans) {
cout << c << "\n";
}
return 0;
}