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

提出ソース

結果

問題	No.5022 XOR Printer
ユーザー	Sor4chi
提出日時	2025-07-26 16:49:16
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,955 ms / 2,000 ms
コード長	10,577 bytes
コンパイル時間	5,444 ms
コンパイル使用メモリ	367,008 KB
実行使用メモリ	7,716 KB
スコア	5,095,529,890
最終ジャッジ日時	2025-07-26 16:51:04
合計ジャッジ時間	106,849 ms
ジャッジサーバーID （参考情報）	judge6 / judge5
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

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

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:319:23: warning: ‘void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >]’ is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
  319 |         random_shuffle(all.begin(), all.end());
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from main.cpp:2:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

ソースコード

raw source code

#pragma GCC optimize("O3,Ofast,omit-frame-pointer,unroll-all-loops,tree-loop-vectorize,tree-slp-vectorize")
#include <bits/stdc++.h>
using namespace std;

string to_binary(int x) {
    string res;
    for (int i = 0; i < 20; ++i) {
        res += (x & (1 << i)) ? '1' : '0';
    }
    reverse(res.begin(), res.end());
    return res;
}

void recursive_comb(int *indexes, int s, int rest, std::function<void(int *)> f) {
    if (rest == 0) {
        f(indexes);
    } else {
        if (s < 0) return;
        recursive_comb(indexes, s - 1, rest, f);
        indexes[rest - 1] = s;
        recursive_comb(indexes, s - 1, rest - 1, f);
    }
}

// nCkの組み合わせに対して処理を実行する
void foreach_comb(int n, int k, std::function<void(int *)> f) {
    int indexes[k];
    recursive_comb(indexes, n - 1, k, f);
}

int dist(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

vector<pair<int, int>> get_tour(vector<pair<int, int>> &to_visit, int sx, int sy, int ex, int ey, int N) {
    // sx,syからex,eyまでのツアーを最短貪欲で求める
    vector<int> tour;
    int cx = sx, cy = sy;
    set<int> visited;
    while (visited.size() < to_visit.size()) {
        int min_dist = 1e9;
        int min_idx = -1;
        for (int i = 0; i < to_visit.size(); ++i) {
            int nx = to_visit[i].first;
            int ny = to_visit[i].second;
            if (visited.count(i)) continue;
            int d = dist(nx, ny, cx, cy);
            if (d < min_dist) {
                min_dist = d;
                min_idx = i;
            }
        }
        if (min_idx == -1) {
            break;
        }
        tour.push_back(min_idx);
        visited.insert(min_idx);
        cx = to_visit[min_idx].first;
        cy = to_visit[min_idx].second;
    }
    vector<pair<int, int>> res;
    for (int i = 0; i < tour.size(); ++i) {
        res.push_back(to_visit[tour[i]]);
    }
    return res;
}

vector<char> get_ops(int sx, int sy, int ex, int ey) {
    vector<char> ops;
    int cx = sx, cy = sy;
    while (cx != ex || cy != ey) {
        if (cx < ex) {
            ops.push_back('D');
            cx++;
        } else if (cx > ex) {
            ops.push_back('U');
            cx--;
        }
        if (cy < ey) {
            ops.push_back('R');
            cy++;
        } else if (cy > ey) {
            ops.push_back('L');
            cy--;
        }
    }
    return ops;
}

pair<vector<char>, int> solve_greedy(vector<pair<int, int>> &target_list, vector<pair<int, int>> &base_list, vector<vector<int>> &_A, int N) {
    vector<vector<int>> A = _A;
    vector<char> ops;

    map<pair<int, int>, vector<int>> op_list;

    // target_listそれぞれで、基底(base_list)のXOR組み合わせで最も値が大きくなるものを選ぶ
    for (auto [x, y] : target_list) {
        int max_val = A[x][y];
        vector<int> op;
        for (int max_k = 1; max_k <= 2; ++max_k) {
            foreach_comb(base_list.size(), max_k, [&](int *v) {
                int val = A[x][y];
                for (int k = 0; k < max_k; ++k) {
                    val ^= A[base_list[v[k]].first][base_list[v[k]].second];
                }
                if (val > max_val) {
                    max_val = val;
                    op = vector<int>(v, v + max_k);
                }
            });
        }
        op_list[{x, y}] = op;
    }

    // target_listから順番に、配っていく
    int cx = 1, cy = 1;
    for (int i = 0; i < base_list.size(); ++i) {
        // 行かなきゃいけない座標リスト
        vector<pair<int, int>> to_visit;
        for (auto [x, y] : target_list) {
            bool found = false;
            for (auto op : op_list[{x, y}]) {
                if (op == i) {
                    found = true;
                    break;
                }
            }
            if (found) {
                to_visit.push_back({x, y});
            }
        }
        int tx = base_list[i].first, ty = base_list[i].second;
        // opsにget_ops(cx, cy, tx, ty)を追加
        for (auto op : get_ops(cx, cy, tx, ty)) {
            ops.push_back(op);
        }
        cx = tx;
        cy = ty;
        assert(cx >= 1 && cx <= N && cy >= 1 && cy <= N);
        assert(tx >= 1 && tx <= N && ty >= 1 && ty <= N);
        vector<pair<int, int>> tour = get_tour(to_visit, tx, ty, tx, ty, N);
        ops.push_back('C');
        int cur = A[tx][ty];
        for (auto [x, y] : tour) {
            vector<char> path = get_ops(cx, cy, x, y);
            assert(x >= 1 && x <= N && y >= 1 && y <= N);
            for (auto op : path) {
                ops.push_back(op);
            }
            cx = x;
            cy = y;
            ops.push_back('W');
            A[cx][cy] ^= cur;
        }
        for (auto op : get_ops(cx, cy, tx, ty)) {
            ops.push_back(op);
        }
        cx = tx;
        cy = ty;
        ops.push_back('C');
    }

    // target_listをbase_listにする
    vector<pair<int, int>> new_target_list;
    new_target_list = base_list;
    // base_list をtarget_listから10個選ぶ
    base_list.clear();
    for (int i = 0; i < new_target_list.size(); ++i) {
        base_list.push_back(target_list[i]);
    }
    target_list = new_target_list;

    // target_listそれぞれで、基底(base_list)のXOR組み合わせで最も値が大きくなるものを選ぶ
    for (auto [x, y] : target_list) {
        int max_val = A[x][y];
        vector<int> op;
        for (int max_k = 1; max_k <= 4; ++max_k) {
            foreach_comb(base_list.size(), max_k, [&](int *v) {
                int val = A[x][y];
                for (int k = 0; k < max_k; ++k) {
                    val ^= A[base_list[v[k]].first][base_list[v[k]].second];
                }
                if (val > max_val) {
                    max_val = val;
                    op = vector<int>(v, v + max_k);
                }
            });
        }
        op_list[{x, y}] = op;
    }

    // target_listから順番に、配っていく
    for (int i = 0; i < base_list.size(); ++i) {
        // 行かなきゃいけない座標リスト
        vector<pair<int, int>> to_visit;
        for (auto [x, y] : target_list) {
            bool found = false;
            for (auto op : op_list[{x, y}]) {
                if (op == i) {
                    found = true;
                    break;
                }
            }
            if (found) {
                to_visit.push_back({x, y});
            }
        }
        int tx = base_list[i].first, ty = base_list[i].second;
        // opsにget_ops(cx, cy, tx, ty)を追加
        for (auto op : get_ops(cx, cy, tx, ty)) {
            ops.push_back(op);
        }
        cx = tx;
        cy = ty;
        assert(cx >= 1 && cx <= N && cy >= 1 && cy <= N);
        assert(tx >= 1 && tx <= N && ty >= 1 && ty <= N);
        vector<pair<int, int>> tour = get_tour(to_visit, tx, ty, tx, ty, N);
        ops.push_back('C');
        int cur = A[tx][ty];
        for (auto [x, y] : tour) {
            vector<char> path = get_ops(cx, cy, x, y);
            assert(x >= 1 && x <= N && y >= 1 && y <= N);
            for (auto op : path) {
                ops.push_back(op);
            }
            cx = x;
            cy = y;
            ops.push_back('W');
            A[cx][cy] ^= cur;
        }
        for (auto op : get_ops(cx, cy, tx, ty)) {
            ops.push_back(op);
        }
        cx = tx;
        cy = ty;
        ops.push_back('C');
    }

    // sum of A
    int score = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            score += A[i][j];
        }
    }

    return {ops, score};
}

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

    int N, T;
    cin >> N >> T;
    vector<vector<int>> A(N + 1, vector<int>(N + 1));
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            cin >> A[i][j];

    chrono::system_clock::time_point start = chrono::system_clock::now();

    vector<char> best_ops;
    int best_score = 0;

    for (int base_x = 1; base_x <= N; ++base_x) {
        vector<pair<int, int>> base_list;
        vector<pair<int, int>> target_list;
        // x=base_x
        for (int y = 1; y <= N; ++y) {
            base_list.push_back({base_x, y});
        }
        // x!=base_x
        for (int x = 1; x <= N; ++x) {
            for (int y = 1; y <= N; ++y) {
                if (x == base_x) continue;
                target_list.push_back({x, y});
            }
        }

        auto [ops, score] = solve_greedy(target_list, base_list, A, N);
        if (score > best_score && ops.size() <= T) {
            best_score = score;
            best_ops = ops;
        }
    }

    for (int base_y = 1; base_y <= N; ++base_y) {
        vector<pair<int, int>> base_list;
        vector<pair<int, int>> target_list;
        // y=base_y
        for (int x = 1; x <= N; ++x) {
            base_list.push_back({x, base_y});
        }
        // y!=base_y
        for (int x = 1; x <= N; ++x) {
            for (int y = 1; y <= N; ++y) {
                if (y == base_y) continue;
                target_list.push_back({x, y});
            }
        }

        auto [ops, score] = solve_greedy(target_list, base_list, A, N);
        if (score > best_score && ops.size() <= T) {
            best_score = score;
            best_ops = ops;
        }
    }

    vector<pair<int, int>> all;
    for (int x = 1; x <= N; ++x) {
        for (int y = 1; y <= N; ++y) {
            all.push_back({x, y});
        }
    }

    // 残り時間いっぱい、base_listを乱択で選んで、それぞれで貪欲
    while (chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() < 1950) {
        random_shuffle(all.begin(), all.end());
        int pick_num = rand() % 10 + 5;
        // 最初のrandom(5,15)個をbase_listにする
        vector<pair<int, int>> base_list;
        for (int i = 0; i < pick_num; ++i) {
            base_list.push_back(all[i]);
        }
        vector<pair<int, int>> target_list;
        for (int i = pick_num; i < all.size(); ++i) {
            target_list.push_back(all[i]);
        }
        auto [ops, score] = solve_greedy(target_list, base_list, A, N);
        if (score > best_score && ops.size() <= T) {
            best_score = score;
            best_ops = ops;
        }
    }

    cerr << "ops.size(): " << best_ops.size() << endl;
    cerr << "score: " << best_score << endl;

    for (auto op : best_ops) cout << op << endl;

    return 0;
}

yukicoder

結果

コンパイルメッセージ

ソースコード