結果

問題 No.5022 XOR Printer
ユーザー aa36
提出日時 2025-07-26 14:29:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 4,193 bytes
コンパイル時間 1,991 ms
コンパイル使用メモリ 208,608 KB
実行使用メモリ 7,720 KB
スコア 4,713,438,814
最終ジャッジ日時 2025-07-26 14:29:14
合計ジャッジ時間 5,713 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*

No.5022 XOR Printer
20bit分考えるらしい
上bitから変更していくと良いのかも？

*/

#include<bits/stdc++.h>
using namespace std;
using ll = long long;//int型は使わない
using vecl = vector<ll>;
using graph = vector<vector<ll>>;
using pll = pair<ll , ll>;
const ll inf = (1LL<<61); //約2e18
const ll MOD = 998244353;
const vecl dx={1,0,-1,0};
const vecl dy={0,1,0,-1};
#define rep(i,a,b) for(ll i=(ll)a; i<(ll)b; i++)
#define rrep(i,a,b) for(ll i=(ll)b-1; i>=(ll)a; i--)
#define all(vec1) (vec1).begin(), (vec1).end()
#define debug(var) cerr << #var << " : " << var << endl;
template<typename... Args>
void eerr(Args&&... args){
    ((std::cerr << args << ' '), ...) << '\n';
}
template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    v.clear();
    std::string line;
    std::getline(is >> std::ws, line); // 1行丸ごと読み込み
    std::stringstream ss(line);
    T x;
    while (ss >> x) {
        v.push_back(x);
    }
    return is;
}
//fastio
struct FastIO {
    FastIO() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} fastio;
//modulo
template<typename T>
T ovr(T a,T b){
  T ret=a%b;
  if(ret<0)ret+=b;
  return ret;
}

///variable
ll n,t;
ll s = 0;
graph a;
void ReadInput(){
    cin >> n >> t;
    a.resize(n) ;
    rep(i,0,n){rep(j,0,n){ll x;cin >> x;a[i].push_back(x);}}
}

ll g_now_x(ll gr_id){
    return gr_id / n;
}
ll g_now_y(ll gr_id){
    if(gr_id / n % 2 == 0){
        return gr_id % n;
    }else{
        return n - 1 - gr_id % n;
    }
}
void inc(){
    t -- ;
    if(t == 0)exit(0);
}
void debug_binary(ll x, const string& label = "") {
    if (!label.empty()) cerr << label << " : ";
    for (ll i = 20 - 1; i >= 0; --i) {
        cerr << ((x >> i) & 1);
    }
    cerr << " (" << x << ")\n";
}

void pri_move(ll ax , ll ay , ll bx , ll by){
    if(ax < bx){
        for(ll _ = bx - ax ; _-- ; ){
            cout << "D" << endl;inc();
        }
    }else{
        for(ll _ = ax - bx ; _-- ; ){
            cout << "U" << endl;inc();
        }
    }
    if(ay < by){
        for(ll _ = by - ay ; _-- ; ){
            cout << "R" << endl;inc();
        }
    }else{
        for(ll _ = ay - by ; _-- ; ){
            cout << "L" << endl;inc();
        }
    }
}
vector<pll> get_best_combination(ll g) {
    ll n = a.size();
    vector<pll> result = {};
    ll best_score = inf;
    if((s>>g)&1){
        best_score = s;
    }

    // 1個だけ
    rep(i1, 0, n) rep(j1, 0, n) {
        ll bitsum = a[i1][j1] ^ s;
        if (((bitsum >> g) & 1) == 1) {
            if (bitsum < best_score) {
                best_score = bitsum;
                result = { {i1, j1} };
            }
        }
    }

    // 2個
    rep(i1, 0, n) rep(j1, 0, n)
    rep(i2, 0, n) rep(j2, 0, n) {
        ll bitsum = a[i1][j1] ^ a[i2][j2] ^ s;
        if (((bitsum >> g) & 1) == 1) {
            if (bitsum < best_score) {
                best_score = bitsum;
                result = { {i1, j1}, {i2, j2} };
            }
        }
    }

    // 3個
    rep(i1, 0, n) rep(j1, 0, n)
    rep(i2, 0, n) rep(j2, 0, n)
    rep(i3, 0, n) rep(j3, 0, n) {
        ll bitsum = a[i1][j1] ^ a[i2][j2] ^ a[i3][j3] ^ s;
        if (((bitsum >> g) & 1) == 1) {
            if (bitsum < best_score) {
                best_score = bitsum;
                result = { {i1, j1}, {i2, j2}, {i3, j3} };
            }
        }
    }

    if(best_score == inf)return {{-1,-1}} ;
    return result;
}

ll nx = 0 , ny = 0 ;
void bit(ll g){
    //sのg bit目を1にする
    vector<pll> vb = get_best_combination(g) ;
    if(vb[0].first==-1)return ;//不可能
    for(pll x : vb){
        pri_move(nx , ny , x.first , x.second) ;
        cout << "C" << endl;inc();
        nx = x.first , ny = x.second ;
        s^=a[x.first][x.second];
    }
    debug_binary(s);
    
    rep(i,0,n*n-1){
        pri_move(nx , ny , g_now_x(i) , g_now_y(i));
        nx = g_now_x(i) , ny = g_now_y(i) ;
        if((a[nx][ny]^s) > (a[nx][ny])){
            cout << "W" << endl;inc();
            a[nx][ny] ^= s ;
        }
    }
}
int main()
{
    ReadInput();
    rrep(i,1,20)bit(i) ;
    cerr << t << endl;
    return 0;
}
0