結果

問題 No.5022 XOR Printer
ユーザー Khun
提出日時 2025-07-26 15:28:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 3,953 bytes
コンパイル時間 2,222 ms
コンパイル使用メモリ 205,088 KB
実行使用メモリ 7,720 KB
スコア 5,186,452,557
最終ジャッジ日時 2025-07-26 15:28:47
合計ジャッジ時間 4,914 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;

class TimeKeeper {
public:
    // コンストラクタ：limitMillis に制限時間（ミリ秒）を指定
    TimeKeeper(long long limitMillis)
        : limitTime(limitMillis), startTime(std::chrono::steady_clock::now())
    {
    }

    // インスタンス生成直後は経過時間は0ミリ秒とみなす

    // 現在の経過時間（ミリ秒）を返す
    long long getNowTime() const {
        auto now = std::chrono::steady_clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(now - startTime);
        return elapsed.count();
    }

    // 制限時間を超えているかを返す
    bool isTimeOver() const {
        return getNowTime() >= limitTime.count();
    }

private:
    std::chrono::steady_clock::time_point startTime;     // 開始時間
    std::chrono::milliseconds limitTime;                 // 制限時間（ミリ秒）
};

// 制限時間
int time_threshold = 1950;

// 変数
int n = 10, t = 1000;
vector<vector<int>> mass(n, vector<int>(n));
string ans;
int pos = 0;
int s = 0;

// 関数
void handle_input() {
    cin >> n >> t;
    rep(i, 0, n) rep(j, 0, n) cin >> mass[i][j];
}

string move(int from, int to) {
    int from_i = from / n;
    int from_j = from % n;
    int to_i = to / n;
    int to_j = to % n;

    string res;
    if(from_i < to_i) rep(i, 0, to_i-from_i) res.push_back('D');
    if(from_i > to_i) rep(i, 0, from_i-to_i) res.push_back('U');
    if(from_j < to_j) rep(i, 0, to_j-from_j) res.push_back('R');
    if(from_j > to_j) rep(i, 0, from_j-to_j) res.push_back('L');

    cerr << from_i << " " << from_j << " " << to_i << " " << to_j << endl;
    cerr << res << endl;

    return res;
}

void trial() {
    vector<int> used;
    rrep(bit, 19, 0) {
        {
            int dist = 1001001001;
            int to = -1;
            rep(i, 0, n) rep(j, 0, n) {
                if(find(used.begin(), used.end(), i*n+j) == used.end() and ((mass[i][j]^s)>>bit) & 1 and dist > abs(i-pos/n) + abs(j-pos%n)) {
                    dist = abs(i-pos/n) + abs(j-pos%n);
                    to = i*n+j;
                }
            }
            if(to == -1) continue;

            ans.append(move(pos, to));
            pos = to;
            ans.append("C");
            s = s ^ mass[to/n][to%n];
        }

        vector<int> dests;
        int ok = 0;
        rep(i, 0, n) rep(j, 0, n) {
            int nj = (i & 1) ? n-j-1 : j;
            cerr << nj << endl;
            if(((mass[i][nj]>>bit) & 1) == 0) {
                dests.push_back(i*n + nj);
                if(find(used.begin(), used.end(), i*n+nj) == used.end()) ok = dests.size()-1;
            }
            // cerr << ((mass[i][j] >> bit) & 1) << endl;
        }
        swap(dests[dests.size()-1], dests[ok]);

        rep(i, 0, dests.size()) {
            int to = dests[i];
            ans.append(move(pos, to));
            pos = to;
            if(i != dests.size()-1 or bit == 19) {
                ans.append("W");
                mass[to/n][to%n] = s ^ mass[to/n][to%n];
            } else {
                ans.append("C");
                s ^= mass[to/n][to%n];
                used.push_back(to);
            }
        }

        if(ans.size() > t) break;
    }
}
void answer() {
    rep(i, 0, min(t, (int)ans.size())) cout << ans[i] << endl;
}

int main(void) {
    auto time_keeper = TimeKeeper(time_threshold);

    handle_input();

    while(1) {
        if (time_keeper.isTimeOver()) {
            break;
        }
        trial();
        break;
    }
    answer();
}
0