結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 tnktsyk
|
| 提出日時 | 2025-07-26 14:32:57 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,922 ms / 2,000 ms |
| コード長 | 6,926 bytes |
| コンパイル時間 | 2,763 ms |
| コンパイル使用メモリ | 214,080 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 4,009,322,051 |
| 最終ジャッジ日時 | 2025-07-26 14:34:39 |
| 合計ジャッジ時間 | 101,717 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// ===== XOR Basis (20-bit) =====
struct XorBasis {
static const int B = 20;
int v[B];
bitset<128> used[B];
XorBasis(){ memset(v,0,sizeof(v)); }
void add(int x, const bitset<128>& bs){
bitset<128> c = bs;
for(int b=B-1;b>=0;--b){
if(((x>>b)&1)==0) continue;
if(v[b]==0){ v[b]=x; used[b]=c; return; }
x ^= v[b];
c ^= used[b];
}
}
pair<int, bitset<128>> build(int target) const {
int t = target, made = 0;
bitset<128> sel; sel.reset();
for(int b=B-1;b>=0;--b){
if(((t>>b)&1)==0) continue;
if(v[b]==0) continue;
t ^= v[b];
made ^= v[b];
sel ^= used[b];
}
return {made, sel};
}
};
// score for a given s
static inline long long eval_score(const vector<int>& flatA, int s){
long long sum = 0;
for(int x: flatA){
int y = x ^ s;
sum += (y > x ? y : x);
}
return sum;
}
// move helper
static inline void move_to(int &r,int &c,int tr,int tc, vector<char>& ops){
while(r<tr){ ops.push_back('D'); ++r; }
while(r>tr){ ops.push_back('U'); --r; }
while(c<tc){ ops.push_back('R'); ++c; }
while(c>tc){ ops.push_back('L'); --c; }
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,T; if(!(cin>>N>>T)) return 0; // N=10, T=1000
vector<vector<int>> A(N, vector<int>(N));
for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin>>A[i][j];
// flatten
vector<int> flatA(N*N);
for(int i=0;i<N;i++) for(int j=0;j<N;j++) flatA[i*N+j] = A[i][j];
// --- initial candidates ---
int s0 = 0; // your greedy
for(int i=0;i<N;i++) for(int j=0;j<N;j++) if(s0 < (s0 ^ A[i][j])) s0 ^= A[i][j];
int s1_target = 0; // per-bit gain
for(int b=0;b<20;b++){
int cnt0=0,cnt1=0;
for(int x: flatA){ if((x>>b)&1) cnt1++; else cnt0++; }
if(cnt0 > cnt1) s1_target |= (1<<b);
}
// basis
XorBasis basis;
for(int i=0;i<N;i++) for(int j=0;j<N;j++){
bitset<128> bs; bs.reset(); bs.set(i*N + j);
basis.add(A[i][j], bs);
}
auto [s0_real, cells0] = basis.build(s0);
auto [s1_real, cells1] = basis.build(s1_target);
long long sc0 = eval_score(flatA, s0_real);
long long sc1 = eval_score(flatA, s1_real);
int S = s0_real; bitset<128> needC = cells0; long long bestScore = sc0;
if(sc1 > sc0){ S = s1_real; needC = cells1; bestScore = sc1; }
// ===== Deterministic hill climbing (1,2,3 XOR) =====
auto single_step = [&](int &Sref, long long &cur){
long long base = cur;
int bestIdx = -1; long long bestGain = 0;
for(int i=0;i<N*N;i++){
int ns = Sref ^ flatA[i];
long long sc = eval_score(flatA, ns);
if(sc - base > bestGain){ bestGain = sc - base; bestIdx = i; }
}
if(bestGain>0){ Sref ^= flatA[bestIdx]; cur += bestGain; return true; }
return false;
};
auto pair_step = [&](int &Sref, long long &cur){
long long base = cur; long long bestGain = 0; int bi=-1,bj=-1;
for(int i=0;i<N*N;i++){
for(int j=i+1;j<N*N;j++){
int ns = Sref ^ flatA[i] ^ flatA[j];
long long sc = eval_score(flatA, ns);
if(sc - base > bestGain){ bestGain=sc-base; bi=i; bj=j; }
}
}
if(bestGain>0){ Sref ^= flatA[bi]; Sref ^= flatA[bj]; cur += bestGain; return true; }
return false;
};
auto triple_step = [&](int &Sref, long long &cur){
long long base = cur; long long bestGain = 0; int bi=-1,bj=-1,bk=-1;
for(int i=0;i<N*N;i++){
for(int j=i+1;j<N*N;j++){
for(int k=j+1;k<N*N;k++){
int ns = Sref ^ flatA[i] ^ flatA[j] ^ flatA[k];
long long sc = eval_score(flatA, ns);
if(sc - base > bestGain){ bestGain=sc-base; bi=i; bj=j; bk=k; }
}
}
}
if(bestGain>0){ Sref ^= flatA[bi]; Sref ^= flatA[bj]; Sref ^= flatA[bk]; cur += bestGain; return true; }
return false;
};
// loop until no improvement
while(true){
if(single_step(S, bestScore)) continue;
if(pair_step(S, bestScore)) continue;
if(triple_step(S, bestScore)) continue;
break;
}
// ===== Optional random search within time budget =====
auto start = chrono::steady_clock::now();
mt19937 rng(1234567);
auto time_ok = [&](){
return chrono::duration<double>(chrono::steady_clock::now()-start).count() < 1.85; // adjust margin
};
vector<int> idxs(N*N); iota(idxs.begin(), idxs.end(), 0);
while(time_ok()){
int k = 1 + (rng()%4); // 1..4 elements
shuffle(idxs.begin(), idxs.end(), rng);
int ns = S;
for(int i=0;i<k;i++) ns ^= flatA[idxs[i]];
long long sc = eval_score(flatA, ns);
if(sc > bestScore){
S = ns; bestScore = sc;
// after a random improvement, run deterministic singles again
while(true){
if(single_step(S, bestScore)) continue;
if(pair_step(S, bestScore)) continue;
if(triple_step(S, bestScore)) continue;
break;
}
}
}
// rebuild for final S
auto [S_real, cells_final] = basis.build(S);
if(S_real != S){
long long sc_real = eval_score(flatA, S_real);
if(sc_real >= bestScore){ S = S_real; bestScore = sc_real; needC = cells_final; }
else needC = cells_final; // keep S; slight mismatch unlikely but allow
} else {
needC = cells_final;
}
// ===== Construct operations =====
vector<char> ops;
int r=0,c=0;
// snake path
vector<pair<int,int>> snake; snake.reserve(N*N);
for(int i=0;i<N;i++){
if(i%2==0) for(int j=0;j<N;j++) snake.emplace_back(i,j);
else for(int j=N-1;j>=0;j--) snake.emplace_back(i,j);
}
if(!snake.empty()){
move_to(r,c, snake[0].first, snake[0].second, ops);
for(size_t k=0;k<snake.size();k++){
int rr = snake[k].first, cc = snake[k].second;
int id = rr*N + cc;
if(needC.test(id)) ops.push_back('C');
if(k+1<snake.size()){
auto [nr,nc] = snake[k+1];
move_to(r,c,nr,nc,ops);
}
}
}
// reverse snake for W
if(!snake.empty()){
for(size_t k=0;k<snake.size();k++){
auto [rr,cc] = snake[snake.size()-1-k];
if(k>0) move_to(r,c, rr, cc, ops);
int x = A[rr][cc];
if( (x ^ S) > x ) ops.push_back('W');
}
}
if((int)ops.size() > T) ops.resize(T); // unlikely, but safeguard
for(char ch: ops) cout << ch << '\n';
return 0;
}