結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 Akidai
|
| 提出日時 | 2025-07-27 14:39:13 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 12,565 bytes |
| コンパイル時間 | 4,800 ms |
| コンパイル使用メモリ | 269,508 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 5,006,266,923 |
| 最終ジャッジ日時 | 2025-07-27 14:40:52 |
| 合計ジャッジ時間 | 98,009 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 48 WA * 2 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = (1LL << 62) - (1LL << 31) - 1;
#define REP(i, init, n) for(int i = (int)(init); i < (int)(n); i++)
#define RREP(i, init, n) for(int i = (int)(init); i >= (int)(n); i--)
#define All(A) A.begin(), A.end()
#define rAll(A) A.rbegin(), A.rend()
#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>
int N, T;
vvi A;
namespace Annealing {
bool is_online_judge() {
return true;
}
class TimeKeeper {
public:
std::chrono::high_resolution_clock::time_point m_start_time;
int64_t m_time_threshold;
int64_t dev_env_threshold;
int dev_const = 1;
TimeKeeper(): m_start_time(std::chrono::high_resolution_clock::now()) {
if(!is_online_judge()) {
dev_const = 1;
}
}
void set_time_threshold(const int64_t &time_threshold) {
m_time_threshold = time_threshold;
dev_env_threshold = time_threshold * dev_const;
}
bool is_time_over() {
using std::chrono::duration_cast;
using std::chrono::milliseconds;
auto diff = std::chrono::high_resolution_clock::now() - (this->m_start_time);
return duration_cast<milliseconds>(diff).count() >= time_threshold();
}
int cur_time() {
using std::chrono::duration_cast;
using std::chrono::milliseconds;
auto diff = std::chrono::high_resolution_clock::now() - (this->m_start_time);
return duration_cast<milliseconds>(diff).count();
}
long double elapsed_ratio() {
return (long double)(this -> cur_time()) / time_threshold();
}
int64_t time_threshold() {
if(!is_online_judge()) {
return dev_env_threshold;
}
return m_time_threshold;
}
};
class Temperature {
private:
long double m_initial_temperature;
long double m_last_temperature;
int init_elapsed;
TimeKeeper tk;
public:
Temperature(const long double &initial_temperature, const long double &last_temperature, const TimeKeeper &tk):
m_initial_temperature(initial_temperature),
m_last_temperature(last_temperature),
tk(tk) {
init_elapsed = this->tk.cur_time();
}
long double get_temperature() {
long double ratio = (long double)(tk.cur_time() - init_elapsed) / (tk.time_threshold() - init_elapsed);
return m_initial_temperature + (m_last_temperature - m_initial_temperature) * ratio;
}
long double prob(const long double &delta) {
return exp(-delta / get_temperature());
}
bool changed(const long double &delta) {
return (delta <= 0) || (rand() < prob(delta) * RAND_MAX);
}
};
}
int calc_dist(const pint &a, const pint &b) {
return abs(a.first - b.first) + abs(a.second - b.second);
}
int calc_score(pint &cur, vector<pint> &targets, vvi &shelter_map) {
pint last = targets.back();
if(shelter_map[last.first][last.second] == 1) {
return 1 << 30;
}
int score = calc_dist(cur, targets[0]);
REP(i, 0, targets.size() - 1) {
score += calc_dist(targets[i], targets[i + 1]);
}
return score;
}
long calc_score2(int b, int s, int rest, pint &cur, vector<pint> &targets) {
long score = 0;
int turn = calc_dist(cur, targets[0]);
if(turn + 1 > rest) {
return score;
}
score += ((A[targets[0].first][targets[0].second] ^ s) & ((1 << b) - 1));
turn++;
REP(i, 1, targets.size()) {
turn += calc_dist(targets[i - 1], targets[i]);
if(turn + 1 > rest) {
break;
}
score += ((A[targets[i].first][targets[i].second] ^ s) & ((1 << b) - 1));
turn++;
}
if(score >= (1 << b) * targets.size()) {
return 0;
}
return score;
}
void move_U(pint &cur, string &ans) {
cur.first--;
ans += 'U';
}
void move_D(pint &cur, string &ans) {
cur.first++;
ans += 'D';
}
void move_L(pint &cur, string &ans) {
cur.second--;
ans += 'L';
}
void move_R(pint &cur, string &ans) {
cur.second++;
ans += 'R';
}
void write(int &s, pint &cur, string &ans) {
A[cur.first][cur.second] ^= s;
ans += 'W';
}
void copy(int &s, pint &cur, string &ans) {
s ^= A[cur.first][cur.second];
ans += 'C';
}
void move(pint &cur, const pint &next, string &ans) {
while(cur != next) {
if(cur.first < next.first) {
move_D(cur, ans);
} else if(cur.first > next.first) {
move_U(cur, ans);
} else if(cur.second < next.second) {
move_R(cur, ans);
} else if(cur.second > next.second) {
move_L(cur, ans);
}
}
}
void solve() {
pint cur = {0, 0};
int s = 0;
int move_count = 0;
string ans = "";
vector<pint> shelters;
vvi shelters_map(N, vi(N, 0));
Annealing::TimeKeeper tk;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
RREP(b, 19, 10) {
int mask = (1 << b);
int min_dist = 100;
pint next_target = {-1, -1};
// cerr << "cur: " << cur.first << " " << cur.second << " s: " << s << " mask: " << bitset<20>(mask) << endl;
REP(i, 0, N) {
REP(j, 0, N) {
if(shelters_map[i][j] == 1) continue;
if(s & mask) {
if((A[i][j] & mask) == 0) {
int dist = calc_dist(cur, {i, j});
if(dist < min_dist) {
min_dist = dist;
next_target = {i, j};
}
}
} else {
if(A[i][j] & mask) {
int dist = calc_dist(cur, {i, j});
if(dist < min_dist) {
min_dist = dist;
next_target = {i, j};
}
}
}
}
}
// cerr << "next_target: " << next_target.first << " " << next_target.second << endl;
if(next_target.first == -1) {
break;
}
move(cur, next_target, ans);
copy(s, cur, ans);
if(ans.size() >= T) break;
cerr << b << " " << cur.first << " " << cur.second << " " << s << endl;
cerr << bitset<20>(s) << endl;
vvi board(N, vi(N, 0));
int rest = 0;
vector<pint> targets;
REP(i, 0, N) {
REP(j, 0, N) {
if(A[i][j] & mask) {
board[i][j] = 1;
} else {
targets.push_back({i, j});
rest++;
}
}
}
tk.set_time_threshold(196 * (20 - b));
Annealing::Temperature temp(10, 0, tk);
int best_score = calc_score(cur, targets, shelters_map);
int cur_score = best_score;
int itr = 0, update_cnt = 0;
while(!tk.is_time_over()) {
int p = mt() % targets.size();
int q = mt() % targets.size();
if(p == q) continue;
itr++;
swap(targets[p], targets[q]);
int new_score = calc_score(cur, targets, shelters_map);
if(temp.changed(new_score - cur_score)) {
update_cnt++;
cur_score = new_score;
if(new_score < best_score) {
best_score = new_score;
}
} else {
swap(targets[p], targets[q]);
}
}
cerr << "itr: " << itr << " update_cnt: " << update_cnt << " best_score: " << best_score << " targets: " << targets.size() << endl;
if(best_score + targets.size() + ans.size() >= T && b >= 11) {
cerr << "final optimization" << endl;
tk.set_time_threshold(196 * (20 - b + 1));
int rest_turn = T - ans.size();
Annealing::Temperature temp2(2000, 0, tk);
long best_score2 = calc_score2(b, s, rest_turn, cur, targets);
cerr << "init best_score2: " << best_score2 << endl;
long cur_score2 = best_score2;
int itr2 = 0, update_cnt2 = 0;
while(!tk.is_time_over()) {
int p = mt() % targets.size();
int q = mt() % targets.size();
if(p == q) continue;
itr2++;
swap(targets[p], targets[q]);
long new_score2 = calc_score2(b, s, rest_turn, cur, targets);
if(temp2.changed(cur_score2 - new_score2)) {
update_cnt2++;
cur_score2 = new_score2;
if(new_score2 > best_score2) {
best_score2 = new_score2;
// cerr << "new best_score2: " << best_score2 << endl;
}
} else {
swap(targets[p], targets[q]);
}
}
// cerr << "itr2: " << itr2 << " update_cnt2: " << update_cnt2 << " best_score2: " << best_score2 << endl;
}
REP(i, 0, targets.size()) {
pint target = targets[i];
move(cur, target, ans);
if(ans.size() >= T) break;
if(i == targets.size() - 1 && b < 19) {
shelters.push_back(cur);
shelters_map[cur.first][cur.second] = 1;
copy(s, cur, ans);
break;
}
write(s, cur, ans);
}
if(ans.size() >= T) break;
/*
REP(i, 0, N) {
REP(j, 0, N) {
cerr << bitset<20>(A[i][j]) << " ";
}
cerr << endl;
}
*/
}
int min_a = 1 << 30;
pint min_pos = {-1, -1};
REP(i, 0, N) {
REP(j, 0, N) {
if(A[i][j] < min_a) {
min_a = A[i][j];
min_pos = {i, j};
}
}
}
pint last_target = {-1, -1};
int min_dist = 100;
REP(i, 0, N) {
REP(j, 0, N) {
if(A[i][j] < ((1 << 19) + (1 << 18))) continue;
int dist = calc_dist(cur, {i, j});
if(dist < min_dist) {
min_dist = dist;
last_target = {i, j};
}
}
}
int len = 0;
cur = {0, 0};
REP(i, 0, ans.size()) {
char c = ans[i];
if(c == 'U') {
cur.first--;
} else if(c == 'D') {
cur.first++;
} else if(c == 'L') {
cur.second--;
} else if(c == 'R') {
cur.second++;
}
if(i < 970) continue;
int last_turn = calc_dist(cur, last_target) + calc_dist(last_target, min_pos) + 4;
if(i + 1 + last_turn > T) {
if(c == 'U') {
cur.first++;
} else if(c == 'D') {
cur.first--;
} else if(c == 'L') {
cur.second++;
} else if(c == 'R') {
cur.second--;
}
cerr << "last_target: " << last_target.first << " " << last_target.second << endl;
cerr << "last_turn: " << last_turn << endl;
break;
}
len = i + 1;
}
ans = ans.substr(0, len);
move(cur, last_target, ans);
copy(s, cur, ans);
move(cur, min_pos, ans);
write(s, cur, ans);
copy(s, cur, ans);
write(s, cur, ans);
long final_score = 0;
REP(i, 0, N) {
REP(j, 0, N) {
final_score += A[i][j];
}
}
cerr << "final score: " << final_score << endl;
if(ans.size() >= T) {
ans = ans.substr(0, T);
}
for(char c: ans) {
cout << c << endl;
}
}
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> N >> T;
A.resize(N, vi(N));
REP(i, 0, N) {
REP(j, 0, N) {
cin >> A[i][j];
}
}
solve();
}