結果

問題 No.5022 XOR Printer
コンテスト
ユーザー random contestant
提出日時 2025-07-26 14:23:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,605 bytes
コンパイル時間 6,304 ms
コンパイル使用メモリ 315,056 KB
実行使用メモリ 7,720 KB
スコア 0
最終ジャッジ日時 2025-07-26 14:23:54
合計ジャッジ時間 8,722 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
// #pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
using vl = vector<ll>;
using vvl = vector<vl>;
using P = pair<ll,ll>;
#define pb push_back
#define int long long
// #define double long double
#define INF (ll) 3e18
// Ctrl + Shift + B コンパイル
// Ctrl + C 中断
// ./m 実行


// No.5022 XOR Printer

int N = 10;
int T = 1000;
vvl a(10, vl(10));

void input() {
  cin >> N >> T;
  rep(i, 10) rep(j, 10) cin >> a[i][j];
}

int score() {
  int res = 0;
  for(auto x : a) for(auto y : x) res += y;
  return res;
}

void solve(){
  int s = 0;                    // 現在の s
  int remain = T;               // 残り手数
  int now_i = 0, now_j = 0;     // 今いるマス (0-indexed)
  string ops;                   // 出力バッファ

  /*―― 移動ユーティリティ ――*/
  auto move_to = [&](int ti, int tj){
    while(now_i < ti && remain){ ops.push_back('D'); ++now_i; --remain; }
    while(now_i > ti && remain){ ops.push_back('U'); --now_i; --remain; }
    while(now_j < tj && remain){ ops.push_back('R'); ++now_j; --remain; }
    while(now_j > tj && remain){ ops.push_back('L'); --now_j; --remain; }
  };

  for(int bit = 19; bit >= 0 && remain; --bit){

    /*==============================*
     * ① 「上位 0・当該 bit だけ 1」の s を作る
     *    ‑ 最大 3 要素まで XOR ‑
     *==============================*/
    struct Cell{int i,j; ll v;};
    vector<Cell> cells;
    for(int i=0;i<10;++i) for(int j=0;j<10;++j) cells.push_back({i,j,a[i][j]});

    bool updated = false;          // この bit を立てられたか

    /*-- 1 要素 --*/
    for(auto &c: cells){
      ll ns = s ^ c.v;
      if(((ns>>(bit+1))==0) && ((ns>>bit)&1)){
        move_to(c.i,c.j); if(!remain) break;
        ops.push_back('C'); --remain;  s = ns;
        updated = true; break;
      }
    }

    /*-- 2 要素 --*/
    if(!updated){
      for(size_t p=0; p<cells.size() && !updated; ++p){
        for(size_t q=p+1; q<cells.size() && !updated; ++q){
          ll ns = s ^ cells[p].v ^ cells[q].v;
          if(((ns>>(bit+1))==0) && ((ns>>bit)&1)){
            move_to(cells[p].i,cells[p].j); if(!remain) {updated=true; break;}
            ops.push_back('C'); --remain;  s ^= cells[p].v;

            move_to(cells[q].i,cells[q].j); if(!remain) {updated=true; break;}
            ops.push_back('C'); --remain;  s ^= cells[q].v;

            updated = true;
          }
        }
      }
    }

    /*-- 3 要素 --*/
    if(!updated){
      for(size_t p=0; p<cells.size() && !updated; ++p){
        for(size_t q=p+1; q<cells.size() && !updated; ++q){
          for(size_t r=q+1; r<cells.size() && !updated; ++r){
            ll ns = s ^ cells[p].v ^ cells[q].v ^ cells[r].v;
            if(((ns>>(bit+1))==0) && ((ns>>bit)&1)){
              move_to(cells[p].i,cells[p].j); if(!remain){updated=true; break;}
              ops.push_back('C'); --remain;  s ^= cells[p].v;

              move_to(cells[q].i,cells[q].j); if(!remain){updated=true; break;}
              ops.push_back('C'); --remain;  s ^= cells[q].v;

              move_to(cells[r].i,cells[r].j); if(!remain){updated=true; break;}
              ops.push_back('C'); --remain;  s ^= cells[r].v;

              updated = true;
            }
          }
        }
      }
    }
    bitset<20> bst;
    bst = s;
    cerr << bst << endl;
    /* 失敗時は何もせず次の bit へ進む */

    /*==============================*
     * ② 現在の s で盤面を蛇行して貪欲に W
     *==============================*/
    bool rev = false;            // 偶数行→, 奇数行←
    for(int i=0;i<10 && remain;++i){
      if(!rev){
        for(int j=0;j<10 && remain;++j){
          move_to(i,j);
          ll nv = a[i][j] ^ s;
          if(nv > a[i][j] && remain){
            ops.push_back('W'); --remain;  a[i][j] = nv;
          }
        }
      }else{
        for(int j=9;j>=0 && remain;--j){
          move_to(i,j);
          ll nv = a[i][j] ^ s;
          if(nv > a[i][j] && remain){
            ops.push_back('W'); --remain;  a[i][j] = nv;
          }
        }
      }
      rev = !rev;
    }
  }

  /*=========== 出力 ===========*/
  cout << ops.size() << '\n';
  for(size_t i=0;i<ops.size();++i){
    cout << ops[i] << (i+1==ops.size()?'\n':' ');
  }
}


signed main(){
  input();
  solve();
}

// 上の桁から埋めていくのが正しそう
0