結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 tnktsyk
|
| 提出日時 | 2025-07-26 14:24:14 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 4 ms / 2,000 ms |
| コード長 | 6,217 bytes |
| コンパイル時間 | 2,171 ms |
| コンパイル使用メモリ | 210,068 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 4,009,308,976 |
| 最終ジャッジ日時 | 2025-07-26 14:24:20 |
| 合計ジャッジ時間 | 4,955 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// ---------- XOR Basis for up to 20 bits ----------
struct XorBasis {
static const int B = 20;
int v[B]; // basis value
bitset<128> used[B]; // cells set that forms this basis vector
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; // cannot set this bit
t ^= v[b];
made ^= v[b];
sel ^= used[b];
}
return {made, sel};
}
};
// score for a given s: sum of max(A[i], A[i]^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 (0-indexed coords)
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 A for fast eval
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];
// ---------- Candidate s0: your greedy "if(s<s^x) s^=x" ----------
int s0 = 0;
for(int i=0;i<N;i++) for(int j=0;j<N;j++) if(s0 < (s0 ^ A[i][j])) s0 ^= A[i][j];
// ---------- Candidate s1: per-bit gain ********
int s1_target = 0;
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);
}
// ---------- Build 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; // start from the better of s0_real, s1_real
bitset<128> needC = cells0;
long long bestScore = sc0;
if(sc1 > sc0){ S = s1_real; needC = cells1; bestScore = sc1; }
// ---------- Hill climbing: single & pair XOR (non-decreasing only) ----------
// single XOR
bool improved = true;
while(improved){
improved = false;
long long cur = bestScore;
int bestIdx = -1; long long addGain = 0;
for(int idx=0; idx<N*N; ++idx){
int ns = S ^ flatA[idx];
long long sc = eval_score(flatA, ns);
if(sc - cur > addGain){
addGain = sc - cur;
bestIdx = idx;
}
}
if(addGain > 0){
S ^= flatA[bestIdx];
bestScore += addGain;
improved = true;
}
}
// pair XOR (optional, still cheap)
bool improved2 = true;
while(improved2){
improved2 = false;
long long cur = bestScore;
long long addGain = 0;
int p = -1, q = -1;
for(int i=0;i<N*N;i++){
for(int j=i+1;j<N*N;j++){
int ns = S ^ flatA[i] ^ flatA[j];
long long sc = eval_score(flatA, ns);
if(sc - cur > addGain){
addGain = sc - cur;
p = i; q = j;
}
}
}
if(addGain > 0){
S ^= flatA[p];
S ^= flatA[q];
bestScore += addGain;
improved2 = true;
}
}
// Rebuild cells for final S (should be representable)
auto [S_real, needC2] = basis.build(S);
if(S_real != S){
// fallback: choose better of (S_real, original S)
long long sc_real = eval_score(flatA, S_real);
if(sc_real >= bestScore){
S = S_real; bestScore = sc_real; needC = needC2;
}else{
// keep S, but still need some C set => build from original S through basis
needC = needC2; // although mismatch rare, allow anyway
}
}else{
needC = needC2;
}
// ---------- Build operation sequence ----------
vector<char> ops;
int r=0, c=0; // current pos (0-indexed -> (1,1) in problem statement)
// Phase 1: traverse snake once, perform C when needed
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);
}
}
}
// Phase 2: reverse snake to W (we are now at last cell already)
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');
}
}
// Safety
if((int)ops.size() > T){
// We shouldn't exceed, but trim if necessary (may break correctness though)
ops.resize(T);
}
for(char ch: ops) cout << ch << '\n';
return 0;
}