結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2025-07-26 16:58:54 |
| 言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,987 ms / 2,000 ms |
| コード長 | 10,049 bytes |
| コンパイル時間 | 6,470 ms |
| コンパイル使用メモリ | 175,964 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,208,442,588 |
| 最終ジャッジ日時 | 2025-07-26 17:03:00 |
| 合計ジャッジ時間 | 109,149 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,T b){
if(a>b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmax(T &a,T b){
if(a<b){
a=b;
return true;
}
return false;
}
namespace Timer{
chrono::system_clock::time_point program_start,start;
void program_start_snap(){
program_start=start=chrono::system_clock::now();
}
void snap(){
start=chrono::system_clock::now();
}
int get_ms(){
auto now=chrono::system_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
return ms;
}
int get_ms_all_program(){
auto now=chrono::system_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
return ms;
}
}
//https://ei1333.github.io/library/other/xor-shift.hpp.html
namespace Random{
uint64_t x=88172645463325252;
constexpr uint32_t mask=numeric_limits<uint32_t>::max();
constexpr double k=1.0/(double)(numeric_limits<uint64_t>::max());
inline uint64_t xorshift64(){
x^=x<<7;
x^=x>>9;
return x;
}
inline uint32_t rand_int(uint32_t r){ //[0,r)
assert(r!=0);
return (xorshift64()&mask)*r>>32;
}
inline int rand_int(int l,int r){ //[l,r)
assert(l<=r);
return l+rand_int(r-l);
}
inline double rand_double(){ // [0.0,1.0]
return xorshift64()*k;
}
}
using Random::rand_int,Random::rand_double;
template<class T> void add(vector<T> &a,const vector<T> b){
for(auto i:b) a.emplace_back(i);
}
constexpr int N=10,T=1000;
int one(int i,int j){
return i*N+j;
}
vector<int> A;
string Operation="UDLRWC";
vector<vector<vector<int>>> path;
vector<vector<int>> dist;
namespace Solver{
int calc_score(const vector<int> &ans){
vector<int> a=A;
int s=0,pos=0;
for(auto i:ans){
if(i==0) pos-=N;
if(i==1) pos+=N;
if(i==2) pos--;
if(i==3) pos++;
if(i==4) a[pos]^=s;
if(i==5) s^=a[pos];
}
int sum=0;
rep(i,N*N) sum+=a[i];
return sum;
}
void solve(){
vector<int> ord;
rep(i,N){
vector<int> v(N);
rep(j,N){
v[j]=one(i,j);
}
if(i&1) reverse(all(v));
add(ord,v);
}
vector<int> a=A;
vector<int> ans;
int s=0,pos=0;
vector<int> used_b0(N*N,false);
int best_score=0;
vector<int> best_ans;
constexpr int time_limit=220;
for(int bit=19;1<=bit;bit--){
if(!(s&(1<<bit))){
if(bit!=19){
int idx=-1,min_dist=INF;
for(auto i:ord){
if(!used_b0[i]&&!(a[i]&(1<<bit))){
if(chmin(min_dist,dist[pos][i])) idx=i;
}
}
if(idx==-1) continue;
add(ans,path[pos][idx]);
pos=idx;
ans.push_back(5);
s^=a[pos];
idx=-1;
pii mn={INF,INF};
for(auto i:ord){
if(!used_b0[i]&&a[i]&(1<<bit)){
int cnt=0;
rep(j,N*N){
int x=a[j];
if(!(a[j]&(1<<bit))) x^=(s^a[i]);
if(!(x&(1<<(bit-1)))) cnt++;
}
if(chmin(mn,{cnt,dist[pos][i]})) idx=i;
}
}
if(idx==-1) continue;
add(ans,path[pos][idx]);
pos=idx;
ans.push_back(5);
s^=a[pos];
}else{
int idx=-1;
pii mn={INF,INF};
for(auto i:ord){
if(!used_b0[i]&&a[i]&(1<<bit)){
int cnt=0;
rep(j,N*N){
int x=a[j];
if(!(a[j]&(1<<bit))) x^=(s^a[i]);
if(!(x&(1<<(bit-1)))) cnt++;
}
if(chmin(mn,{cnt,dist[pos][i]})) idx=i;
}
}
if(idx==-1) continue;
add(ans,path[pos][idx]);
pos=idx;
ans.push_back(5);
s^=a[pos];
}
}
int b0=-1,b1=-1;
int min_dist=INF;
if(bit!=19){
for(auto i:ord){
if(!(a[i]&(1<<bit))&&!used_b0[i]){
if(chmin(min_dist,dist[ord.back()][i])) b0=i;
}
}
used_b0[b0]=true;
}
int last=b0;
if(b0==-1) last=ord.back();
vector<int> tour;
tour.push_back(pos);
min_dist=INF;
for(auto i:ord){
if(i==b0) continue;
if(!used_b0[i]&&chmin(min_dist,dist[last][i])) b1=i;
if(!(a[i]&(1<<bit))){
a[i]^=s;
if(!used_b0[i]&&chmin(min_dist,dist[last][i])) b1=i;
tour.push_back(i);
}
}
if(b0!=-1) tour.push_back(b0);
else tour.push_back(ord.back());
int sz=len(tour);
Timer::snap();
int ms=0;
int loop_cnt=0;
int now_dist=0;
rep(i,sz-1){
now_dist+=dist[tour[i]][tour[i+1]];
}
int best_dist=now_dist;
vector<int> best_tour=tour;
double temp=10;
while(true){
int x=rand_int(1,sz-1),y=rand_int(1,sz-1);
if(x==y) continue;
if(y<x) swap(x,y);
int diff=0;
diff-=dist[tour[x-1]][tour[x]]+dist[tour[y]][tour[y+1]];
diff+=dist[tour[x-1]][tour[y]]+dist[tour[x]][tour[y+1]];
if((loop_cnt&1023)==1023){
ms=Timer::get_ms();
if(time_limit<=ms) break;
temp=10-(double)10/time_limit*ms;
}
double prob=exp(-diff/temp);
if(rand_double()<prob){
reverse(tour.begin()+x,tour.begin()+y+1);
now_dist+=diff;
if(chmin(best_dist,now_dist)) best_tour=tour;
}
loop_cnt++;
}
tour=best_tour;
replr(i,1,sz-1){
add(ans,path[pos][tour[i]]);
ans.push_back(4);
pos=tour[i];
}
if(bit!=19){
if(b0==-1) break;
vector<int> if_ans=ans;
add(if_ans,path[pos][b0]);
if_ans.push_back(4);
if(T<len(if_ans)) if_ans.resize(T);
if(chmax(best_score,calc_score(if_ans))) best_ans=if_ans;
add(ans,path[pos][b0]);
pos=b0;
ans.push_back(5);
s^=a[pos];
add(ans,path[pos][b1]);
pos=b1;
ans.push_back(5);
s^=a[pos];
}else{
ans.push_back(5);
s^=a[pos];
}
reverse(all(ord));
if(T<len(ans)) break;
if(chmax(best_score,calc_score(ans))) best_ans=ans;
}
if(T<len(ans)) ans.resize(T);
if(chmax(best_score,calc_score(ans))) best_ans=ans;
cerr << Timer::get_ms_all_program() << endl;
cerr << best_score << endl;
/*rep(i,N){
rep(j,N){
cerr << bitset<20>(a[one(i,j)]) << " ";
}
cerr << endl;
}*/
for(auto i:best_ans) cout << Operation[i] << '\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
Timer::program_start_snap();
int n,t;
cin >> n >> t;
A.resize(N*N);
rep(i,N*N) cin >> A[i];
path.resize(N*N,vector<vector<int>>(N*N));
dist.resize(N*N,vector<int>(N*N,0));
rep(ai,N){
rep(aj,N){
rep(bi,N){
rep(bj,N){
vector<int> v;
if(ai<bi){
rep(_,bi-ai) v.push_back(1);
}else{
rep(_,ai-bi) v.push_back(0);
}
if(aj<bj){
rep(_,bj-aj) v.push_back(3);
}else{
rep(_,aj-bj) v.push_back(2);
}
path[one(ai,aj)][one(bi,bj)]=v;
dist[one(ai,aj)][one(bi,bj)]=len(v);
}
}
}
}
Solver::solve();
exit(0);
}