提出 6cc894c7-25f4-4a6d-9cb8-f4f227eebfe5

コード

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;

typedef array<int, 2> xy;

struct Op
{
    int id, H, W, a, b;
};

struct ApplyOp
{
    int op_idx, x, y;
};

struct State
{
    vector<vector<int>> A;
    vector<ApplyOp> applied_ops;
    int score;
    array<char, 3000> used;
};

int calc_score(const vector<vector<int>> &A, const vector<vector<int>> &B)
{
    int score = 0;
    int N = A.size();
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            int diff = (int)A[i][j] - (int)B[i][j];
            score += diff * diff;
        }
    }
    return score;
}

int N, T;

void solve1()
{
    vector<vector<int>> A(N, vector<int>(N)), B(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> A[i][j];
    auto atmp = A;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> B[i][j];
    vector<Op> ops(T);
    for (int t = 0; t < T; ++t)
    {
        ops[t].id = t;
        cin >> ops[t].H >> ops[t].W >> ops[t].a >> ops[t].b;
    }
    const int LIMIT = 100000;

    clock_t clk = clock();
    struct XORShiftRandom
    {
        uint64_t x = 88172645463325252ULL;
        inline uint64_t operator()()
        {
            x ^= x << 13;
            x ^= x >> 7;
            x ^= x << 17;
            return x;
        }
        using result_type = uint64_t;
        constexpr static result_type min() { return 0; }
        constexpr static result_type max() { return UINT64_MAX; }
    } rng;

    array<vector<int>, 50> val_to_op;
    for (int i = 0; i < T; ++i)
    {
        val_to_op[ops[i].a].push_back(i);
    }

    array<char, 3000> used;
    used.fill(0);
    vector<ApplyOp> applied_ops;
    int score = calc_score(A, B);
    array<int, 50> candidates;
    candidates.fill(0);
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            int diff = (int)A[i][j] - (int)B[i][j];
            candidates[A[i][j]] += diff * diff;
        }
    }

    while ((double)(clock() - clk) / CLOCKS_PER_SEC < 2.8)
    {
        for (int i = 0; i < 49; i++)
            candidates[i + 1] += candidates[i];
        int val = rng() % candidates.back();
        int tar;
        for (tar = 0; tar < 50; tar++)
        {
            if (candidates[tar] >= val)
                break;
        }
        int id = val_to_op[tar][rng() % val_to_op[tar].size()], H = ops[id].H, W = ops[id].W, a = ops[id].a, b = ops[id].b;
        if (used[id] < 3)
        {
            vector<vector<int>> pref(N + 1, vector<int>(N + 1, 0));
            bool anyPossible = false;
            for (int i = 0; i < N; ++i)
            {
                int rowSum = 0;
                for (int j = 0; j < N; ++j)
                {
                    int w = 0;
                    if (A[i][j] == a)
                    {
                        int before = (int)a - (int)B[i][j];
                        int after = (int)b - (int)B[i][j];
                        w = after * after - before * before;
                        anyPossible = true;
                    }
                    rowSum += w;
                    pref[i + 1][j + 1] = pref[i][j + 1] + rowSum;
                }
            }
            if (!anyPossible)
                continue;
            int bestDelta = 0;
            int bestX = -1, bestY = -1;
            for (int x = 0; x + H <= N; ++x)
            {
                for (int y = 0; y + W <= N; ++y)
                {
                    int x2 = x + H, y2 = y + W;
                    int s = pref[x2][y2] - pref[x][y2] - pref[x2][y] + pref[x][y];
                    if (s < bestDelta)
                    {
                        bestDelta = s;
                        bestX = x;
                        bestY = y;
                    }
                }
            }
            if (bestX == -1)
                continue;
            for (int i = bestX; i < bestX + H; ++i)
            {
                for (int j = bestY; j < bestY + W; ++j)
                {
                    if (A[i][j] == a)
                    {
                        int diff = A[i][j] - B[i][j];
                        candidates[A[i][j]] -= diff * diff;
                        A[i][j] = b;
                        diff = A[i][j] - B[i][j];
                        candidates[A[i][j]] += diff * diff;
                    }
                }
            }
            applied_ops.push_back(ApplyOp{id, bestX, bestY});
            ++used[id];
            score += bestDelta;
        }
    }

    cout << applied_ops.size() << "\n";

    for (auto &[op_idx, x, y] : applied_ops)
    {
        cout << op_idx << " " << x << " " << y << "\n";
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> N >> T))
        return 0;
    // if (N <= 20)
    solve1();
    // else
    // solve2();
}
結果

問題	点数	言語	結果	実行時間	メモリ
A - Replace() は Replace() されました	0	C++	RE	111 ms	3748 KiB