結果
| 問題 | No.5022 XOR Printer |
| コンテスト | |
| ユーザー |
 twins_fuyu
|
| 提出日時 | 2026-02-03 06:30:34 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,698 bytes |
| 記録 | |
| コンパイル時間 | 5,504 ms |
| コンパイル使用メモリ | 380,420 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2026-02-03 06:30:44 |
| 合計ジャッジ時間 | 8,682 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 50 |
ソースコード
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "immintrin.h"
using namespace std;
#define rep1(a) for (int _ = 0; _ < (a); ++_)
#define rep2(i, a) for (int i = 0; i < (a); ++i)
#define rep3(i, a, b) for (int i = a; i < (b); ++i)
#define rrep1(a) for (int i = (a) - 1; i >= 0; --i)
#define rrep2(i, a) for (int i = (a) - 1; i >= 0; --i)
#define rrep3(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) overload3(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define in(i, vec) for (auto i : (vec))
template <class T>
using pqueue = priority_queue<T, vector<T>>; // 大きい順
template <class T>
using pqueue_g = priority_queue<T, vector<T>, greater<T>>; // 小さい順
namespace library
{
class xorshift128plus
{
private:
uint64_t s[2];
public:
using result_type = uint64_t;
xorshift128plus(uint64_t seed = 1)
{
seed_gen(seed);
}
void seed(uint64_t seed_val)
{
seed_gen(seed_val);
}
static constexpr result_type min()
{
return std::numeric_limits<result_type>::min();
}
static constexpr result_type max()
{
return std::numeric_limits<result_type>::max();
}
result_type operator()()
{
uint64_t s1 = s[0];
uint64_t s0 = s[1];
s[0] = s0;
s1 ^= s1 << 23;
s[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26);
return s[1] + s0;
}
private:
void seed_gen(uint64_t seed_val)
{
// SplitMix64 で状態2個を初期化
s[0] = splitmix64(seed_val);
s[1] = splitmix64(s[0]);
}
static uint64_t splitmix64(uint64_t &x)
{
x += 0x9E3779B97F4A7C15ULL;
uint64_t z = x;
z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
return z ^ (z >> 31);
}
};
struct Timer
{
chrono::steady_clock::time_point start;
Timer() : start(chrono::steady_clock::now()) {}
double elapse()
{
return chrono::duration<double>(chrono::steady_clock::now() - start).count();
}
bool over(double t)
{
return elapse() > t;
}
bool operator()(double t)
{
return elapse() < t;
}
};
void fast_io()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
uint64_t exp_table[2001];
bool init_exp_table(){
for(int i=0;i<=2000;++i){
exp_table[i]=numeric_limits<uint64_t>::max()*exp(double(-i)/100.0);
}
return true;
}
bool exp_table_initialized = init_exp_table();
uint64_t sa_exp(double diff, double temperature){
if(temperature==0) return 0;
else if (diff>=0) return numeric_limits<uint64_t>::max();
int index = int(-diff * 100.0 / temperature);
if(index>2000) return 0;
return exp_table[index];
}
} // namespace library
uniform_real_distribution<double> rnd(0.0, 1.0);
normal_distribution<double> randn(0.0, 1.0);
library::xorshift128plus rng(12345);
library::Timer timer;
double TL = 1.9;
constexpr int N = 10;
constexpr int NN = N * N;
constexpr int T = 1000;
uint32_t A[N][N];
vector<pair<int,int>> order;
/*
...0123...
...7654...
...89AB...
*/
struct Input{
void get(){
int n,t; cin>>n>>t;
assert(n==N && t==T);
rep(i,N)rep(j,N) cin>>A[i][j];
rep(i,N)rep(j,N) order.emplace_back(i,j);
}
};
Input input;
int clz20(uint32_t bit){
return bit==0?20:__builtin_clz(bit)-12;
}
int cx = 0, cy = 0;
uint32_t s = 0;
string Out;
vector<tuple<int,int,int>> targets = {
{0,0,0},{1,0,1},{2,0,2},{3,0,3},
{4,1,3},{5,1,2},{6,1,1},{7,1,0},
};
int O[N][N] = {};
pair<int,int> iO[NN] = {};
void init_O(){
int cx=0,cy=0;
int o=0;
rep(i,10){
O[cx][cy]=o++;
if(i!=9) cy++;
else cx++;
}
rep(i,2){
rep(j,4){
O[cx][cy]=o++;
cy--;
O[cx][cy]=o++;
cx++;
O[cx][cy]=o++;
cy++;
O[cx][cy]=o++;
cx++;
}
O[cx][cy]=o++; cy--;
O[cx][cy]=o++; cy--;
rep(j,4){
O[cx][cy]=o++;
cy--;
O[cx][cy]=o++;
cy--;
O[cx][cy]=o++;
cx--;
O[cx][cy]=o++;
cy++;
O[cx][cy]=o++;
cy++;
O[cx][cy]=o++;
cx--;
}
O[cx][cy]=o++; cy--;
O[cx][cy]=o++; cy--;
O[cx][cy]=o++; cy--;
}
rep(i,N)rep(j,N){
iO[O[i][j]]={i,j};
}
}
vector<pair<int,int>> get_clz_use(int clz_target){
sort(order.begin(),order.end(),[&](auto a, auto b){
int da = abs(a.first - cx) + abs(a.second - cy);
int db = abs(b.first - cx) + abs(b.second - cy);
int damax = max(abs(a.first - cx), abs(a.second - cy));
int dbmax = max(abs(b.first - cx), abs(b.second - cy));
return damax == dbmax ? da < db : damax < dbmax;
});
for(uint32_t use_bit=0;use_bit<(1u<<16);++use_bit){
uint32_t ns = s;
rep(i,16)if(use_bit>>i&1){
ns ^= A[order[i].first][order[i].second];
}
if(clz20(ns)!=clz_target) continue;
vector<pair<int,int>> res;
rep(i,16)if(use_bit>>i&1){
res.emplace_back(order[i]);
}
return res;
}
cerr << "No use found!" << endl;
return {};
}
vector<pair<int,int>> get_clz_use(int clz_target, int gx, int gy){
sort(order.begin(),order.end(),[&](auto a, auto b){
int da = abs(a.first - gx) + abs(a.second - gy);
int db = abs(b.first - gx) + abs(b.second - gy);
int damax = max(abs(a.first - gx), abs(a.second - gy));
int dbmax = max(abs(b.first - gx), abs(b.second - gy));
return damax == dbmax ? da < db : damax < dbmax;
});
for(uint32_t use_bit=0;use_bit<(1u<<16);++use_bit){
uint32_t ns = s ^ A[gx][gy];
rep(i,16)if(use_bit>>i&1){
ns ^= A[order[i].first][order[i].second];
}
if(clz20(ns)!=clz_target) continue;
vector<pair<int,int>> res;
rep(i,16)if(use_bit>>i&1){
res.emplace_back(order[i]);
}
return res;
}
cerr << "No use found!" << endl;
return {};
}
void go_to(int gx, int gy){
while(cx<gx){
Out+='D';
++cx;
}
while(cx>gx){
Out+='U';
--cx;
}
while(cy<gy){
Out+='R';
++cy;
}
while(cy>gy){
Out+='L';
--cy;
}
}
void copy_s(){
s ^= A[cx][cy];
Out+='C';
}
void write_s(){
A[cx][cy] ^= s;
Out+='W';
}
// Manhattan distance
int mht(const pair<int,int>& a, const pair<int,int>& b){
return abs(a.first - b.first) + abs(a.second - b.second);
};
string print_bit(uint32_t x){
string res;
rep(i,20){
res += ((x>>(19-i))&1) ? '1' : '0';
}
return res;
}
void use_step(const vector<pair<int,int>>& use){
// insert tsp
vector<pair<int,int>> path;
path.emplace_back(cx,cy);
for(auto p: use){
int best_diff = 1e9;
int best_pos = -1;
rep(i,path.size()){
int prev_dist = i==path.size()-1 ? 0: mht(path[i], path[i+1]);
int new_dist = mht(path[i], p) + (i==path.size()-1 ? 0 : mht(p, path[i+1]));
int diff = new_dist - prev_dist;
if(diff<best_diff){
best_diff = diff;
best_pos = i+1;
}
}
path.insert(path.begin()+best_pos, p);
}
cerr << "use size: " << use.size() << ", path size: " << path.size() << endl;
rep(i,1,path.size()){
go_to(path[i].first, path[i].second);
copy_s();
}
cerr << "clz used: " << clz20(s) << " s = " << print_bit(s) << endl;
}
void write_step(){
int start_order = O[cx][cy];
rep(d,NN){
int no = (start_order + d) % NN;
auto [nx, ny] = iO[no];
if(nx < 3 || ny < 3) continue;
uint32_t a = A[nx][ny];
uint32_t na = a ^ s;
if(a<na){
go_to(nx, ny);
write_s();
}
}
}
void print_A(){
rep(i,N)rep(j,N){
rep(k,20) cerr << ((A[i][j]>>(19-k))&1);
cerr << (j==N-1?"\n":" ");
}
}
int main(){
library::fast_io();
input.get();
init_O();
rep(i,N)rep(j,N){
cerr << (O[i][j] < 10 ? " " : "") << O[i][j] << (j==N-1?"\n":" ");
}
rep(clz_target,9){
go_to(min(3, cx), min(3, cy));
auto clz_use = get_clz_use(clz_target);
use_step(clz_use);
write_step();
cerr << Out.size() << " steps after clz " << clz_target << endl;
}
rep(i,3)rep(j,3){
uint32_t a = A[i][j];
uint32_t ma = a;
uint32_t max_bit = 0;
for(int bit=0;bit<512;++bit){
uint32_t na = s^a;
rep(k,3)rep(l,3)if(bit&(1<<(k*3+l))){
na ^= A[k][l];
}
if(na>ma){
ma = na;
max_bit = bit;
}
}
rep(k,3)rep(l,3)if(max_bit&(1<<(k*3+l))){
go_to(k,l);
copy_s();
}
go_to(i,j);
write_s();
}
print_A();
cerr << Out.size() << " steps in total" << endl;
if(Out.size()>T){
Out = Out.substr(0,T);
}
cout << Out << endl;
return 0;
}