結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 syndrome
|
| 提出日時 | 2025-07-26 16:59:55 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,960 ms / 2,000 ms |
| コード長 | 16,468 bytes |
| コンパイル時間 | 5,373 ms |
| コンパイル使用メモリ | 337,648 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,212,104,942 |
| 最終ジャッジ日時 | 2025-07-26 17:06:08 |
| 合計ジャッジ時間 | 106,983 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
// (◕ᴗ◕✿)
// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define srep(i, s, n) for (ll i = s; i < (n); ++i)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = 3.141592653589793;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;
#define debug(var) do{std::cout << #var << " : \n";view(var);}while(0)
template<typename T> void view(T e){cout << e << endl;}
template<typename T> void view(const vc<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;}
template<typename T> void view(const vv<T>& vv){ for(const auto& v : vv){ view(v); } }
// #define DEBUG
#ifdef DEBUG
constexpr bool DEBUGMODE = true;
#else
constexpr bool DEBUGMODE = false;
#endif
ofstream wrt;
string outputfile = "output.txt", inputfile = "input.txt";
unsigned int randxor(){
static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
unsigned int t;
t = (x ^ (x << 11)); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int randint(int a, int b) {return(a + randxor() % (b - a));}
struct Timer {
public:
Timer(int limit){
start = chrono::high_resolution_clock::now();
goal = start + chrono::milliseconds(limit);
}
inline double rate(){
return (chrono::high_resolution_clock::now() - start).count() / (double)(goal - start).count();
}
inline int get_time(){return (chrono::high_resolution_clock::now() - start).count() / 1e6;}
private:
chrono::high_resolution_clock::time_point start;
chrono::high_resolution_clock::time_point goal;
};
ll hilbertorder(int x, int y, ll maxn) {
ll rx, ry, d = 0;
for (ll s = maxn >> 1; s; s >>= 1) {
rx = (x & s)>0, ry = (y & s)>0;
d += s * s * ((rx * 3) ^ ry);
if (ry) continue;
if (rx) {
x = maxn - 1 - x;
y = maxn - 1 - y;
}
swap(x, y);
}
return d;
}
template<class T, int CAP> struct CapArr {
int sz = 0;
T arr[CAP];
CapArr() {}
T& operator[](int i) { return arr[i]; }
const T& operator[](int i) const { return arr[i]; }
void push_back(const T& x){
arr[sz] = x;
sz++;
}
void pop_back(){sz--;}
void resize(int x){sz = x;}
void clear(){sz = 0;}
void shuffle(){
rep(i, sz - 1) swap(arr[i], arr[i + randint(0, sz - i)]);
}
template<int nCAP> void copy(const CapArr<T, nCAP> &A){
memcpy(arr, A.arr, sizeof(T) * A.sz);
sz = A.sz;
}
void sort(){std::sort(arr, arr + sz);}
void insert(int index, const T* mem, int size) {
if (index == sz) {
memcpy(arr + index, mem, sizeof(T) * size);
sz += size;
}
else {
memmove(arr + index + size, arr + index, sizeof(T) * (sz - index));
memcpy(arr + index, mem, sizeof(T) * size);
sz += size;
}
}
void multi_insert(int index, const T& val, int count) {
// if (sz + count > CAP) return;
if (index != sz) {
memmove(arr + index + count, arr + index, sizeof(T) * (sz - index));
}
std::fill(arr + index, arr + index + count, val);
sz += count;
}
void remove(int start, int end) {
int size = end - start;
memmove(arr + start, arr + end, sizeof(T) * (sz - end));
sz -= size;
}
void RemoveInsert(int start, int end, const T* p, int size) {
int newEnd = start + size;
if (sz - end > 0 && newEnd != end) {
memmove(arr + newEnd, arr + end, sizeof(T) * (sz - end));
}
memcpy(arr + start, p, sizeof(T) * size);
sz -= end - start;
sz += size;
}
const T back(){return arr[sz - 1];}
const int size()const{return sz;}
};
//https://topcoder-tomerun.hatenablog.jp/entry/2021/06/12/134643
//改造済み...
template<int length_MAX, int element_MAX> struct IndexSet {
CapArr<int, length_MAX> que;
int pos[element_MAX];
IndexSet() {
rep(i, element_MAX) pos[i] = -1;
}
int operator[](int i)const{return que[i];}
void add(int v) {
if (pos[v] == -1){
pos[v] = que.sz;
que.push_back(v);
}
}
void remove(int v) {
int p = pos[v];
int b = que.back();
que.arr[p] = b;
que.pop_back();
pos[b] = p;
pos[v] = -1;
}
bool contains(int v) const {
return pos[v] != -1;
}
int size() const {
return que.sz;
}
};
double log_table[70000];
//variable
constexpr int TIME_LIMIT = 1940;
constexpr int N = 10;
constexpr int M = 100;
constexpr int T = 1000;
array<int, M> A;
vi topbit[20];
array<int, M> eval;
vi order;
int mark[M];
namespace simulated_annealing {
constexpr int transition_num = 5;
int transition_count[transition_num];
int success_count[transition_num];
using Cost = int;
struct Config {
int time_limit;
int temperature_type;
double start_temp, goal_temp;
int probability[transition_num];
};
struct State {
Cost score;
IndexSet<10, M> used;
vi indexs;
vvi path;
State(){
score = -inf;
}
void operator=(const State &other) {
score = other.score;
indexs = other.indexs;
}
void init(){
used = IndexSet<10, M>();
indexs = {topbit[16][0], topbit[17][0], topbit[18][0], topbit[19][0], topbit[19][1], topbit[19][2]};
used.add(topbit[16][0]);
used.add(topbit[17][0]);
used.add(topbit[18][0]);
used.add(topbit[19][0]);
used.add(topbit[19][1]);
used.add(topbit[19][2]);
score = CalcScore();
}
vvi buildans(){
int P = len(indexs);
vi S(1, A[indexs[0]]);
int nscore = 0, length = P + indexs[0] / N + indexs[0] % N;
srep(i, 1, len(indexs)){
S.push_back(S.back() ^ A[indexs[i]]);
length += abs(indexs[i - 1] / N - indexs[i] / N) + abs(indexs[i - 1] % N - indexs[i] % N);
}
vvi paths(P);
rep(i, P) paths[i].push_back(indexs[i]);
vi cmbs(1 << P, 0);
rep(i, 1 << P){
rep(j, P) if (i >> j & 1) cmbs[i] ^= S[j];
}
vi last(P, 0);
rep(i, P) mark[indexs[i]] = i + 1;
for (auto i : order){
int mask = (1 << mark[i]) - 1;
int best = -1, bestcmb = -1;
rep(cmb, 1 << P) if ((mask & cmb) == 0 && (A[i] ^ cmbs[cmb]) > best){
best = A[i] ^ cmbs[cmb];
bestcmb = cmb;
}
rep(j, P) if (bestcmb >> j & 1){
paths[j].push_back(i);
length += abs(i / N - last[j] / N) + abs(i % N - last[j] % N) + 1;
last[j] = i;
}
nscore += best;
// cout << bestcmb << ' ';
// if (i % N == N - 1) cout << endl;
}
rep(i, P){
mark[indexs[i]] = 0;
length += last[i] / N + last[i] % N;
}
// 実際の長さはこれよ真に短くなるはず
if (length > T) nscore = -inf;
return paths;
}
Cost CalcScore(){
int P = len(indexs);
vi S(1, A[indexs[0]]);
int nscore = 0, length = P + indexs[0] / N + indexs[0] % N;
srep(i, 1, len(indexs)){
S.push_back(S.back() ^ A[indexs[i]]);
length += abs(indexs[i - 1] / N - indexs[i] / N) + abs(indexs[i - 1] % N - indexs[i] % N);
}
vi cmbs(1 << P, 0);
rep(i, 1 << P){
rep(j, P) if (i >> j & 1) cmbs[i] ^= S[j];
}
vi last(P, 0);
rep(i, P) mark[indexs[i]] = i + 1;
for (auto i : order){
int mask = (1 << mark[i]) - 1;
int best = -1, bestcmb = -1;
rep(cmb, 1 << P) if ((mask & cmb) == 0 && (A[i] ^ cmbs[cmb]) > best){
best = A[i] ^ cmbs[cmb];
bestcmb = cmb;
}
rep(j, P) if (bestcmb >> j & 1){
length += abs(i / N - last[j] / N) + abs(i % N - last[j] % N) + 1;
last[j] = i;
}
nscore += best;
// cout << bestcmb << ' ';
// if (i % N == N - 1) cout << endl;
}
rep(i, P){
mark[indexs[i]] = 0;
length += last[i] / N + last[i] % N;
}
// 実際の長さはこれよ真に短くなるはず
if (length > T) nscore = -inf;
return nscore;
}
void transition01(Cost &threshold){
transition_count[0]++;
int id = randint(0, len(indexs)), tp = randint(15, 20);
while (len(topbit[tp]) == 0) tp = randint(15, 20);
int tpi = randint(0, len(topbit[tp]));
if (used.contains(topbit[tp][tpi])) return;
int last = indexs[id];
indexs[id] = topbit[tp][tpi];
auto new_score = CalcScore();
if (new_score >= threshold){
success_count[0]++;
score = new_score;
used.remove(last);
used.add(indexs[id]);
}else{
indexs[id] = last;
}
}
void transition02(Cost &threshold){ // swap
transition_count[1]++;
int id = randint(0, len(indexs)), jd = randint(0, len(indexs));
while (id == jd){
jd = randint(0, len(indexs));
}
swap(indexs[id], indexs[jd]);
auto new_score = CalcScore();
if (new_score >= threshold){
success_count[1]++;
score = new_score;
}else{
swap(indexs[id], indexs[jd]);
}
}
void transition03(Cost &threshold){ // push
transition_count[2]++;
int tp = 19;
int tpi = randint(0, len(topbit[tp]));
if (used.contains(topbit[tp][tpi])) return;
indexs.push_back(topbit[tp][tpi]);
auto new_score = CalcScore();
if (new_score >= threshold){
success_count[2]++;
score = new_score;
used.add(indexs.back());
}else{
indexs.pop_back();
}
}
void transition04(Cost &threshold){ // pop
transition_count[3]++;
int id = randint(0, len(indexs));
vi lstindex = indexs;
indexs.erase(indexs.begin() + id);
auto new_score = CalcScore();
if (new_score >= threshold){
success_count[3]++;
score = new_score;
used.remove(lstindex[id]);
}else{
swap(indexs, lstindex);
}
}
void transition05(Cost &threshold){ // kick
transition_count[4]++;
Cost p = score - 2e7;
rep(i, 3) transition01(p);
success_count[4]++;
}
};
State simulated_annealing(const Config& config, State state) {
State best;
Timer timer(config.time_limit);
int roop = 0;
double tmp = config.start_temp;
double rate = 0;
while (true){
roop++;
int randomint = randint(0, 1000);
Cost threshold = state.score + tmp * log_table[randint(0, 70000)];
if (randomint < config.probability[0]){ // transition 01
state.transition01(threshold);
}else if (randomint < config.probability[1]){
state.transition02(threshold);
}else if (randomint < config.probability[2]){
state.transition03(threshold);
}else if (randomint < config.probability[3]){
state.transition04(threshold);
}else{
state.transition05(threshold);
}
if (best.score < state.score){ // update best
best = state;
}
if (roop % 1000 == 0){
// if (roop % 10000 == 0) cerr << state.score << " " << best.score << endl;
rate = timer.rate();
if (config.temperature_type == 0){
tmp = config.start_temp + rate * (config.goal_temp - config.start_temp);
}else{
tmp = config.start_temp * pow(config.goal_temp / config.start_temp, rate);
}
if (rate > 1.0){
break;
}
}
}
cerr << "roop : " << roop << endl;
cerr << "score : " << best.score << endl;
rep(i, transition_num) cerr << "transition" << i << " conversion rate : " << fixed << setprecision(4) << success_count[i] / (double)transition_count[i] * 100 << " % " << success_count[i] << " / " << transition_count[i] << endl;
return best;
};
}// namespace simulated_annealing
struct Solver{
simulated_annealing::State ans;
void input(){
if (DEBUGMODE){
ifstream in(inputfile);
cin.rdbuf(in.rdbuf());
int a; cin >> a >> a;
rep(i, M) cin >> A[i];
}else{
int a; cin >> a >> a;
rep(i, M) cin >> A[i];
}
}
void init(){
double n = 1 / (double)(2 * 70000);
for (int i = 0; i < 70000; i++) {
log_table[i] = log(((double)i / 70000) + n);
}
rep(i, M) topbit[31 - __builtin_clz(A[i])].push_back(i);
ll maxn = 1;
while (maxn < N) maxn <<= 1;
rep(i, N){
srep(j, 1, N) eval[i * N + j] = hilbertorder(i, j - 1, maxn) + 1;
}
int s = eval[(N - 1) * N + 1];
for (int i = N - 1; i >= 0; i--){
s++;
eval[i * N] = s;
}
eval[0] = 0;
order.resize(M); iota(all(order), 0);
sort(all(order), [&](auto i, auto j){return eval[i] < eval[j];});
}
void move(int s, int t){
if (DEBUGMODE){
while (s / N < t / N){
wrt << 'D' << endl;
s += N;
}
while (s / N > t / N){
wrt << 'U' << endl;
s -= N;
}
while (s % N < t % N){
wrt << 'R' << endl;
s++;
}
while (s % N > t % N){
wrt << 'L' << endl;
s--;
}
}else{
while (s / N < t / N){
cout << 'D' << endl;
s += N;
}
while (s / N > t / N){
cout << 'U' << endl;
s -= N;
}
while (s % N < t % N){
cout << 'R' << endl;
s++;
}
while (s % N > t % N){
cout << 'L' << endl;
s--;
}
}
}
void output(){
rep(p, len(ans.path)){
int frst = ans.path[p][0];
sort(all(ans.path[p]), [&](auto i, auto j){ return eval[i] < eval[j];});
int id = 0;
rep(i, len(ans.path[p])) if (ans.path[p][i] == frst){id = i; break;}
rotate(ans.path[p].begin(), ans.path[p].begin() + id, ans.path[p].end());
}
int pos = 0;
for (auto p : ans.path){
rep(i, len(p)){
move(pos, p[i]);
pos = p[i];
if (DEBUGMODE){
if (i == 0) wrt << 'C' << endl;
else wrt << 'W' << endl;
}else{
if (i == 0) cout << 'C' << endl;
else cout << 'W' << endl;
}
}
}
}
void run(){
Timer timer(TIME_LIMIT);
input();
init();
simulated_annealing::Config config = {
TIME_LIMIT - timer.get_time(),
0,
15.0,
0.0,
{850, 960, 975, 990, 1000}
};
simulated_annealing::State state;
state.init();
ans = simulated_annealing::simulated_annealing(config, state);
ans.path = ans.buildans();
rep(i, len(ans.indexs)){
cerr << A[ans.indexs[i]] << ' ' << 31 - __builtin_clz(A[ans.indexs[i]]) << endl;
}
output();
}
};
int main(){
wrt.open(outputfile, ios::out);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Solver solver;
solver.run();
wrt.close();
return 0;
}