結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 ぬるぽ
|
| 提出日時 | 2025-07-26 15:17:53 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,563 ms / 2,000 ms |
| コード長 | 9,282 bytes |
| コンパイル時間 | 4,256 ms |
| コンパイル使用メモリ | 307,920 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,083,346,097 |
| 最終ジャッジ日時 | 2025-07-26 15:19:01 |
| 合計ジャッジ時間 | 67,748 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
// greedy_xor_v12.cpp
// ------------------------------------------------------------------
// • 80 万台 / 90 万台セルを 2 マスずつ残す制約は維持
// • **a 候補を 2 つ選び，現在位置から近い方** を採用
// 1. まず “残数 > reserve” を満たす 80/90 万台セルを
// 値が小さい順に最大 2 個収集（high 候補）
// 2. 足りなければその他セルから値が小さい順に追加して計 2 個に
// 3. その 2 個のうち，Manhattan 距離が短い方を a とする
// • stderr には各ステップ詳細 + 最終スコア + 総ステップ数
// • stdout は提出用操作列（1 行 1 文字）
// ------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_COST12 = 30;
constexpr int MAX_COST3 = 45;
constexpr int LOW80 = 800000, HIGH80 = 899999;
constexpr int LOW90 = 900000, HIGH90 = 999999;
struct Plan{
double ratio=-1; int gain=0,cost=0; char type=0;
int ar=0,ac=0,b1r=0,b1c=0,b2r=0,b2c=0,b3r=0,b3c=0;
};
inline int manh(int r1,int c1,int r2,int c2){ return abs(r1-r2)+abs(c1-c2); }
void addMoves(int r1,int c1,int r2,int c2,vector<char>& ops){
if(r2>r1) ops.insert(ops.end(),r2-r1,'D'); else ops.insert(ops.end(),r1-r2,'U');
if(c2>c1) ops.insert(ops.end(),c2-c1,'R'); else ops.insert(ops.end(),c1-c2,'L');
}
bool in80(int v){ return LOW80<=v && v<=HIGH80; }
bool in90(int v){ return LOW90<=v && v<=HIGH90; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int N,T; if(!(cin>>N>>T)) return 0;
vector<vector<int>> A(N,vector<int>(N));
for(auto& row:A) for(int& x:row) cin>>x;
vector<pair<int,int>> cells;
cells.reserve(N*N);
for(int i=0;i<N;i++) for(int j=0;j<N;j++) cells.emplace_back(i,j);
int init80=0, init90=0;
for(auto [i,j]:cells){
int v=A[i][j];
if(in80(v)) ++init80;
else if(in90(v)) ++init90;
}
const int reserve80 = (init80>=2 ? 2 : 0);
const int reserve90 = (init90>=2 ? 2 : 0);
int remain80 = init80, remain90 = init90;
vector<vector<char>> blocked(N,vector<char>(N,0));
int r=0,c=0,s=0;
vector<char> ops;
int step=1;
auto skip_by_reserve=[&](int v){ return (in80(v)&&remain80<=reserve80)||(in90(v)&&remain90<=reserve90); };
while(true){
// ---------- a 候補 2 つを選ぶ ----------
vector<pair<int,int>> high, rest;
for(auto [i,j]:cells){
if(blocked[i][j]) continue;
int v=A[i][j];
bool highFlag = (in80(v)&&remain80>reserve80) || (in90(v)&&remain90>reserve90);
if(highFlag) high.emplace_back(i,j);
else rest.emplace_back(i,j);
}
auto by_val=[&](auto p1,auto p2){ return A[p1.first][p1.second] < A[p2.first][p2.second]; };
std::sort(high.begin(),high.end(),by_val);
std::sort(rest.begin(),rest.end(),by_val);
vector<pair<int,int>> cand;
for(auto p:high){
cand.push_back(p);
if((int)cand.size()==2) break;
}
for(auto p:rest){
cand.push_back(p);
if((int)cand.size()==2) break;
}
if(cand.empty()) break; // 全ブロック済み
// 近い方を a に
int ar=cand[0].first, ac=cand[0].second;
if(cand.size()==2){
int d0=manh(r,c, cand[0].first,cand[0].second);
int d1=manh(r,c, cand[1].first,cand[1].second);
if(d1<d0) { ar=cand[1].first; ac=cand[1].second; }
}
int a_val=A[ar][ac];
Plan best; best.ar=ar; best.ac=ac;
// ---------- 1‑copy ----------
for(auto [br,bc]:cells){
if(br==ar&&bc==ac) continue;
if(skip_by_reserve(A[br][bc])) continue;
int cost=manh(r,c,br,bc)+1+manh(br,bc,ar,ac)+1;
if(cost>MAX_COST12||(int)ops.size()+cost>T) continue;
int gain=(a_val^(s^A[br][bc]))-a_val;
if(gain<=0) continue;
double ratio=(double)gain/cost;
if(ratio>best.ratio) best={ratio,gain,cost,'1',ar,ac,br,bc};
}
// ---------- 2‑copy ----------
for(auto [b1r,b1c]:cells){
if(b1r==ar&&b1c==ac) continue;
if(skip_by_reserve(A[b1r][b1c])) continue;
for(auto [b2r,b2c]:cells){
if((b2r==ar&&b2c==ac)||(b2r==b1r&&b2c==b1c)) continue;
if(skip_by_reserve(A[b2r][b2c])) continue;
int cost=manh(r,c,b1r,b1c)+1+manh(b1r,b1c,b2r,b2c)+1+manh(b2r,b2c,ar,ac)+1;
if(cost>MAX_COST12||(int)ops.size()+cost>T) continue;
int gain=(a_val^(s^A[b1r][b1c]^A[b2r][b2c]))-a_val;
if(gain<=0) continue;
double ratio=(double)gain/cost;
if(ratio>best.ratio) best={ratio,gain,cost,'2',ar,ac,b1r,b1c,b2r,b2c};
}
}
// ---------- 3‑copy ----------
for(auto [b1r,b1c]:cells){
if(b1r==ar&&b1c==ac) continue;
if(skip_by_reserve(A[b1r][b1c])) continue;
for(auto [b2r,b2c]:cells){
if((b2r==ar&&b2c==ac)||(b2r==b1r&&b2c==b1c)) continue;
if(skip_by_reserve(A[b2r][b2c])) continue;
for(auto [b3r,b3c]:cells){
if(b3r==ar&&b3c==ac) continue;
if((b3r==b1r&&b3c==b1c)||(b3r==b2r&&b3c==b2c)) continue;
if(skip_by_reserve(A[b3r][b3c])) continue;
int cost=manh(r,c,b1r,b1c)+1+manh(b1r,b1c,b2r,b2c)+1+
manh(b2r,b2c,b3r,b3c)+1+manh(b3r,b3c,ar,ac)+1;
if(cost>MAX_COST3||(int)ops.size()+cost>T) continue;
int gain=(a_val^(s^A[b1r][b1c]^A[b2r][b2c]^A[b3r][b3c]))-a_val;
if(gain<=0) continue;
double ratio=(double)gain/cost;
if(ratio>best.ratio) best={ratio,gain,cost,'3',ar,ac,b1r,b1c,b2r,b2c,b3r,b3c};
}
}
}
// ---------- 改善手なし → ブロック ----------
if(best.ratio<0){
blocked[ar][ac]=1;
continue;
}
// ---------- ログ ----------
cerr<<"Step "<<step<<": "<<best.type<<"-copy "
<<"a=("<<best.ar+1<<","<<best.ac+1<<") val="<<a_val;
if(best.type=='1'){
cerr<<" | b=("<<best.b1r+1<<","<<best.b1c+1<<") val="<<A[best.b1r][best.b1c];
}else if(best.type=='2'){
cerr<<" | b1=("<<best.b1r+1<<","<<best.b1c+1<<") val="<<A[best.b1r][best.b1c]
<<" | b2=("<<best.b2r+1<<","<<best.b2c+1<<") val="<<A[best.b2r][best.b2c];
}else{
cerr<<" | b1=("<<best.b1r+1<<","<<best.b1c+1<<") val="<<A[best.b1r][best.b1c]
<<" | b2=("<<best.b2r+1<<","<<best.b2c+1<<") val="<<A[best.b2r][best.b2c]
<<" | b3=("<<best.b3r+1<<","<<best.b3c+1<<") val="<<A[best.b3r][best.b3c];
}
cerr<<" | s="<<s<<" | gain="<<best.gain<<"/cost="<<best.cost<<"\n";
// ---------- 残数更新 ----------
if(in80(a_val)) --remain80;
else if(in90(a_val)) --remain90;
auto after_write=[&](int oldv,int newv){
if(in80(oldv)&&!in80(newv)) --remain80;
else if(!in80(oldv)&&in80(newv)) ++remain80;
if(in90(oldv)&&!in90(newv)) --remain90;
else if(!in90(oldv)&&in90(newv)) ++remain90;
};
// ---------- 実行 ----------
if(best.type=='1'){
int vb=A[best.b1r][best.b1c];
addMoves(r,c,best.b1r,best.b1c,ops); ops.push_back('C');
s^=vb; r=best.b1r; c=best.b1c;
addMoves(r,c,ar,ac,ops); ops.push_back('W');
int old=A[ar][ac]; A[ar][ac]^=s; after_write(old,A[ar][ac]);
r=ar; c=ac;
}else if(best.type=='2'){
int vb1=A[best.b1r][best.b1c], vb2=A[best.b2r][best.b2c];
addMoves(r,c,best.b1r,best.b1c,ops); ops.push_back('C');
s^=vb1; r=best.b1r; c=best.b1c;
addMoves(r,c,best.b2r,best.b2c,ops); ops.push_back('C');
s^=vb2; r=best.b2r; c=best.b2c;
addMoves(r,c,ar,ac,ops); ops.push_back('W');
int old=A[ar][ac]; A[ar][ac]^=s; after_write(old,A[ar][ac]);
r=ar; c=ac;
}else{
int vb1=A[best.b1r][best.b1c], vb2=A[best.b2r][best.b2c], vb3=A[best.b3r][best.b3c];
addMoves(r,c,best.b1r,best.b1c,ops); ops.push_back('C');
s^=vb1; r=best.b1r; c=best.b1c;
addMoves(r,c,best.b2r,best.b2c,ops); ops.push_back('C');
s^=vb2; r=best.b2r; c=best.b2c;
addMoves(r,c,best.b3r,best.b3c,ops); ops.push_back('C');
s^=vb3; r=best.b3r; c=best.b3c;
addMoves(r,c,ar,ac,ops); ops.push_back('W');
int old=A[ar][ac]; A[ar][ac]^=s; after_write(old,A[ar][ac]);
r=ar; c=ac;
}
++step;
}
// ---------- 終了ログ ----------
long long total=0;
for(auto& row:A) for(int v:row) total+=v;
cerr<<"Final score: "<<total<<"\n";
cerr<<"Total steps: "<<step-1<<"\n";
// ---------- 出力 ----------
for(char ch:ops) cout<<ch<<'\n';
return 0;
}