#1107739 (C++23) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: butsurizuki
• 提出日時: 2025-07-26 03:30:14
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 7,911 bytes
• コンパイル時間: 4,772 ms
• コンパイル使用メモリ: 316,552 KB
• 実行使用メモリ: 7,716 KB
• スコア: 3,928,768,715
• 最終ジャッジ日時: 2025-07-26 12:46:52
• 合計ジャッジ時間: 6,741 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
other	AC * 50

ソースコード

#include <bits/stdc++.h>
#include <sys/time.h>

using namespace std;

long long start_time;

void start_clock(){
  struct timeval tv;
  gettimeofday(&tv, NULL);
  start_time=(tv.tv_sec*1000000+tv.tv_usec);
}

long long current_clock(){
  struct timeval tv;
  gettimeofday(&tv, NULL);
  long long current_time=(tv.tv_sec*1000000+tv.tv_usec);
  // cout << current_time-start_time << "(us)\n";
  return current_time-start_time;
}

class xrand {
    uint64_t x;

   public:
    using result_type = uint32_t;
    static constexpr result_type min() {
        return std::numeric_limits<result_type>::min();
    }
    static constexpr result_type max() {
        return std::numeric_limits<result_type>::max();
    }
    xrand(uint64_t k) : x(k) {}
    xrand() : xrand(1) {}
    result_type operator()() {
        x ^= x << 9;
        return x ^= x >> 7;
        // return (x * 0x123456789abcdef) >> 32;
    }
    int64_t operator()(int m) { return int64_t((*this)()) * m >> 32; }
    double rand() { return double((*this)()) / (int64_t(1) << 32); }
};

xrand rng;

using pi=pair<int,int>;

int N,T;
vector<vector<int>> A;

void getInput(){
  cin >> N >> T;
  A.resize(N);
  for(auto &nx : A){
    nx.resize(N);
    for(auto &ny : nx){
      cin >> ny;
    }
  }
}

typedef struct{
  string op;
  int s;
  vector<vector<int>> a;
  pi x;
}Game;

Game iniGame(){
  Game res;
  res.op="";
  res.s=0;
  res.a=A;
  res.x.first=0;
  res.x.second=0;
  return res;
}

void output(Game &g){
  for(auto &nx : g.op){
    cout << nx << "\n";
  }
}

void act(char c,Game &g){
  g.op.push_back(c);
  if(c=='U'){g.x.first--;}
  else if(c=='D'){g.x.first++;}
  else if(c=='L'){g.x.second--;}
  else if(c=='R'){g.x.second++;}
  else if(c=='W'){g.a[g.x.first][g.x.second]^=g.s;}
  else if(c=='C'){g.s^=g.a[g.x.first][g.x.second];}
}

int dim(vector<int> a){
  vector<int> base;
  for(auto &nx : a){
    for(auto &ny : base){
      nx=min(nx,nx^ny);
    }
    if(nx>0){base.push_back(nx);}
  }
  return base.size();
}

int sweeping(int s,vector<int> &a){
  int n=a.size();
  vector<pi> base;
  for(int i=0;i<n;i++){
    pi cur={a[i],(1<<i)};
    for(auto &nx : base){
      if(cur.first > (cur.first^nx.first)){
        cur.first^=nx.first;
        cur.second^=nx.second;
      }
    }
    if(cur.first>0){
      base.push_back(cur);
    }
  }

  int res=0;
  for(auto &nx : base){
    if(s > (s^nx.first)){
      s^=nx.first;
      res^=nx.second;
    }
  }
  if(s>0){return -1;}
  return res;
}

int dist(pi a,pi b){
  return abs(a.first-b.first)+abs(a.second-b.second);
}

// s -> (tsp on a) -> f
vector<pi> tsp_grid(pi s,pi f,vector<pi> &a){
  int n=a.size();
  if(n<=15){
    vector<vector<int>> dp(1<<n,vector<int>(n,1e9));
    vector<vector<int>> pre(1<<n,vector<int>(n,-1));
    for(int i=0;i<n;i++){
      dp[(1<<i)][i]=dist(s,a[i]);
      pre[(1<<i)][i]=-1;
    }
    for(int i=0;i<(1<<n);i++){
      for(int j=0;j<n;j++){
        if(dp[i][j]>5e8){continue;}
        for(int k=0;k<n;k++){
          if(i&(1<<k)){continue;}
          int nd=dp[i][j]+dist(a[j],a[k]);
          if(dp[i|(1<<k)][k] > nd){
            dp[i|(1<<k)][k]=nd;
            pre[i|(1<<k)][k]=j;
          }
        }
      }
    }

    int rd=1e9,rp=-1;
    for(int i=0;i<n;i++){
      int nd=dp[(1<<n)-1][i]+dist(a[i],f);
      if(rd>nd){
        rd=nd;
        rp=i;
      }
    }

    vector<pi> res={f};
    int pos=(1<<n)-1;
    while(pos>0){
      int nrp=dp[pos][rp];
      res.push_back(a[rp]);
      pos^=(1<<rp);
      rp=nrp;
    }
    reverse(res.begin(),res.end());

    return res;
  }
  else{
    // wip
    vector<pi> res;
    map<int,vector<pi>> mp;
    for(auto &nx : a){
      mp[nx.first].push_back(nx);
    }
    int fl=0;
    for(auto &nx : mp){
      if(fl){ sort(nx.second.rbegin(),nx.second.rend()); }
      else{ sort(nx.second.begin(),nx.second.end()); }
      fl^=1;
      for(auto &ny : nx.second){ res.push_back(ny); }
    }
    res.push_back(f);
    return res;
  }
}

vector<pi> da={
  {0,0},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{-1,2},{0,2},{1,2},{2,2},{2,1},{2,0},{2,-1},{2,-2},{1,-2},{0,-2},{-1,-2},{-2,-2},{-2,-1},{-2,0},{-2,1},{-2,2},{-2,3},{-1,3},{0,3},{1,3},{2,3},{3,3},{3,2},{3,1},{3,0},{3,-1},{3,-2},{3,-3},{2,-3},{1,-3},{0,-3},{-1,-3},{-2,-3},{-3,-3},{-3,-2},{-3,-1},{-3,0},{-3,1},{-3,2},{-3,3},{-3,4},{-2,4},{-1,4},{0,4},{1,4},{2,4},{3,4},{4,4},{4,3},{4,2},{4,1},{4,0},{4,-1},{4,-2},{4,-3},{4,-4},{3,-4},{2,-4},{1,-4},{0,-4},{-1,-4},{-2,-4},{-3,-4},{-4,-4},{-4,-3},{-4,-2},{-4,-1},{-4,0},{-4,1},{-4,2},{-4,3},{-4,4},{-4,5},{-3,5},{-2,5},{-1,5},{0,5},{1,5},{2,5},{3,5},{4,5},{5,5},{5,4},{5,3},{5,2},{5,1},{5,0},{5,-1},{5,-2},{5,-3},{5,-4},{5,-5},{4,-5},{3,-5},{2,-5},{1,-5},{0,-5},{-1,-5},{-2,-5},{-3,-5},{-4,-5},{-5,-5},{-5,-4},{-5,-3},{-5,-2},{-5,-1},{-5,0},{-5,1},{-5,2},{-5,3},{-5,4},{-5,5},{-5,6},{-4,6},{-3,6},{-2,6},{-1,6},{0,6},{1,6},{2,6},{3,6},{4,6},{5,6},{6,6},{6,5},{6,4},{6,3},{6,2},{6,1},{6,0},{6,-1},{6,-2},{6,-3},{6,-4},{6,-5},{6,-6},{5,-6},{4,-6},{3,-6},{2,-6},{1,-6},{0,-6},{-1,-6},{-2,-6},{-3,-6},{-4,-6},{-5,-6},{-6,-6},{-6,-5},{-6,-4},{-6,-3},{-6,-2},{-6,-1},{-6,0},{-6,1},{-6,2},{-6,3},{-6,4},{-6,5},{-6,6},{-6,7},{-5,7},{-4,7},{-3,7},{-2,7},{-1,7},{0,7},{1,7},{2,7},{3,7},{4,7},{5,7},{6,7},{7,7},{7,6},{7,5},{7,4},{7,3},{7,2},{7,1},{7,0},{7,-1},{7,-2},{7,-3},{7,-4},{7,-5},{7,-6},{7,-7},{6,-7},{5,-7},{4,-7},{3,-7},{2,-7},{1,-7},{0,-7},{-1,-7},{-2,-7},{-3,-7},{-4,-7},{-5,-7},{-6,-7},{-7,-7},{-7,-6},{-7,-5},{-7,-4},{-7,-3},{-7,-2},{-7,-1},{-7,0},{-7,1},{-7,2},{-7,3},{-7,4},{-7,5},{-7,6},{-7,7},{-7,8},{-6,8},{-5,8},{-4,8},{-3,8},{-2,8},{-1,8},{0,8},{1,8},{2,8},{3,8},{4,8},{5,8},{6,8},{7,8},{8,8},{8,7},{8,6},{8,5},{8,4},{8,3},{8,2},{8,1},{8,0},{8,-1},{8,-2},{8,-3},{8,-4},{8,-5},{8,-6},{8,-7},{8,-8},{7,-8},{6,-8},{5,-8},{4,-8},{3,-8},{2,-8},{1,-8},{0,-8},{-1,-8},{-2,-8},{-3,-8},{-4,-8},{-5,-8},{-6,-8},{-7,-8},{-8,-8},{-8,-7},{-8,-6},{-8,-5},{-8,-4},{-8,-3},{-8,-2},{-8,-1},{-8,0},{-8,1},{-8,2},{-8,3},{-8,4},{-8,5},{-8,6},{-8,7},{-8,8},{-8,9},{-7,9},{-6,9},{-5,9},{-4,9},{-3,9},{-2,9},{-1,9},{0,9},{1,9},{2,9},{3,9},{4,9},{5,9},{6,9},{7,9},{8,9},{9,9},{9,8},{9,7},{9,6},{9,5},{9,4},{9,3},{9,2},{9,1},{9,0},{9,-1},{9,-2},{9,-3},{9,-4},{9,-5},{9,-6},{9,-7},{9,-8},{9,-9},{8,-9},{7,-9},{6,-9},{5,-9},{4,-9},{3,-9},{2,-9},{1,-9},{0,-9},{-1,-9},{-2,-9},{-3,-9},{-4,-9},{-5,-9},{-6,-9},{-7,-9},{-8,-9},{-9,-9},{-9,-8},{-9,-7},{-9,-6},{-9,-5},{-9,-4},{-9,-3},{-9,-2},{-9,-1},{-9,0},{-9,1},{-9,2},{-9,3},{-9,4},{-9,5},{-9,6},{-9,7},{-9,8},{-9,9}
};

string genMove(pi x,pi y){
  string res;
  while(x.first<y.first){
    res.push_back('D');
    x.first++;
  }
  while(x.first>y.first){
    res.push_back('U');
    x.first--;
  }
  while(x.second<y.second){
    res.push_back('R');
    x.second++;
  }
  while(x.second>y.second){
    res.push_back('L');
    x.second--;
  }
  return res;
}

bool ins(pi x){
  if(!(0<=x.first && x.first<N)){return false;}
  if(!(0<=x.second && x.second<N)){return false;}
  return true;
}

void move(pi x,Game &g){
  string m=genMove(g.x,x);
  for(auto &nx : m){
    act(nx,g);
  }
}

Game solve(){
  auto g=iniGame();
  {
    pi tg;
    for(auto &nx : da){
      pi cur=g.x;
      cur.first+=nx.first;
      cur.second+=nx.second;
      if(!ins(cur)){continue;}
      if(g.a[cur.first][cur.second]&(1<<19)){
        tg=cur;
        break;
      }
    }
    move(tg,g);
    act('C',g);
    vector<pi> ts;
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        if((g.a[i][j]&(1<<19))==0){
          ts.push_back({i,j});
        }
      }
    }
    ts=tsp_grid(g.x,{0,0},ts);
    for(int i=0;i<ts.size();i++){
      move(ts[i],g);
      if(i!=ts.size()-1){act('W',g);}
    }
  }
  return g;
}

int main(){
  start_clock();
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  getInput();
  auto g=solve();
  output(g);
  int sc=0;
  for(auto &nx : g.a){
    for(auto &ny : nx){
      sc+=ny;
    }
  }
  cerr << sc << "\n";
  return 0;
}