提出 ad1e9712-937c-4a90-a47f-feb16d3cad27

コード

#ifndef INCLUDE_MACRO
#define INCLUDE_MACRO
#include __FILE__

// 山登りに行こう！
random_device get_rand;
int N, T;
vector<vector<int>> A(60, vector<int>(60));
vector<vector<int>> B(60, vector<int>(60));
vector<int> H(3000), W(3000), from(3000, -1), to(3000), rule_count(3000), output_rule, X, Y;
vector<pair<int, int>> HW_larger(3000);

void heat(Timer timer) {
    for (auto p : HW_larger) {
        int i = p.second;
        // 使うルールはi番目
        int best_before_score = -1, best_after_score = -1, best_x = -1, best_y = -1;
        vector<vector<int>> BA(N + 1, vector<int>(N + 1, 0));
        vector<vector<int>> Bto(N + 1, vector<int>(N + 1, 0));
        double heat_x;
        bool change_x;
        rep(h, N) {
            rep(w, N) {
                BA[h + 1][w + 1] = BA[h + 1][w] + (B[h][w] - A[h][w]) * (B[h][w] - A[h][w]);
                if (A[h][w] == from[i]) Bto[h + 1][w + 1] = Bto[h + 1][w] + (B[h][w] - to[i]) * (B[h][w] - to[i]);
                else Bto[h + 1][w + 1] = Bto[h + 1][w] + (B[h][w] - A[h][w]) * (B[h][w] - A[h][w]);
            }
        }
        rep(h, N) {
            rep(w, N) {
                BA[h + 1][w + 1] += BA[h][w + 1];
                Bto[h + 1][w + 1] += Bto[h][w + 1];
            }
        }
        for (int x = 0; x < N - H[i] + 1; x++) {
            for (int y = 0; y < N - W[i] + 1; y++) {
                if (!timer.is_under(2.9)) goto FIN;
                if (rule_count[i] >= 3) goto RE;
                int before_score = BA[H[i] + x][W[i] + y] - BA[H[i] + x][y] - BA[x][W[i] + y] + BA[x][y];
                int after_score = Bto[H[i] + x][W[i] + y] - Bto[H[i] + x][y] - Bto[x][W[i] + y] + Bto[x][y];
                if ((before_score - after_score) > (best_before_score - best_after_score)) {
                    best_before_score = before_score;
                    best_after_score = after_score;
                    best_x = x;
                    best_y = y;
                }
            }
        }
        if (best_x == -1) goto RE;
        heat_x = best_after_score * 1.0 / best_before_score;
        change_x = (get_rand() * 1.0 / (1LL << 32) < heat_x);
        if (change_x) {
            rule_count[i]++;
            output_rule.push_back(i);
            X.push_back(best_x);
            Y.push_back(best_y);
            rep(hh, H[i]) {
                rep(ww, W[i]) {
                    int h = hh + best_x;
                    int w = ww + best_y;
                    if (A[h][w] == from[i]) A[h][w] = to[i];
                }
            }
        }
    RE:;
    }
FIN:
    return;
}

signed main() {
    cin >> N >> T;
    rep(i, N) rep(j, N) cin >> A[i][j];
    rep(i, N) rep(j, N) cin >> B[i][j];
    rep(i, T) {
        cin >> H[i] >> W[i] >> from[i] >> to[i];
        HW_larger[i] = { H[i] * W[i], i };
    }
    Timer timer;
    sort(HW_larger.begin(), HW_larger.end());
    while (T > 0) {
        if (!timer.is_under(2.9)) break;
        heat(timer);
    }
    cout << output_rule.size() << endl;
    rep(i, output_rule.size()) {
        cout << output_rule[i] << " " << X[i] << " " << Y[i] << endl;
    }
    return 0;
}

#else

#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <cmath> // sqrt
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <chrono> // Timer
#include <iomanip> // setprecision
#include <limits> // INT_MAX, LLONG_MAX
#include <random> // random
using namespace std;
#define int long long
#define set_dxy4 std::vector<int> dx4(4); dx4 = {1, -1, 0, 0}; std::vector<int> dy4(4); dy4 = {0, 0, 1, -1}
#define set_dxy8 std::vector<int> dx8(8); dx8 = {1, -1, 0, 0, 1, -1, -1, 1}; std::vector<int> dy8(8); dy8 = {0, 0, 1, -1, 1, -1, 1, -1}
#define under(N) std::fixed << std::setprecision(N)
#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; i++)
#define orep(i, n) for (int i = 1; i <= n; i++)
#define intmod const int mod = 998244353
#define INF (1LL<<60)*3
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int ipow(int x, int y) {
    int ret = 1;
    while (y > 0) {
        if (y % 2 == 1) {
            ret *= x;
        }
        x *= x;
        y >>= 1;
    }
    return ret;
}
int mod_pow(int x, int y, int mod) {
    int ret = 1;
    while (y > 0) {
        if (y % 2 == 1) {
            ret = ret * x % mod;
        }
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
unsigned int isqrt(unsigned int n) {
    if (n == 0) return 0;
    unsigned int rinzi = (unsigned int)(std::sqrt(n)) - 1;
    return rinzi * (rinzi + 2) < n ? rinzi + 1 : rinzi;
}
bool out_glid(int i, int j, int h, int w) {
    if (i < 0 || h <= i || j < 0 || w <= j) return true;
    else return false;
}
class Timer {
    chrono::system_clock::time_point start;
public:
    Timer() : start(chrono::system_clock::now()) {}
    double count() {
        chrono::duration<double> Time_ = chrono::system_clock::now() - start;
        return Time_.count();
    }
    bool is_under(double x) {
        return (this->count()) < x;
    }
};
template<class T>
void allout(T x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}
template<>
void allout(std::map<int, int> x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << (*it).first << " " << (*it).second << "\n";
    }
}
template<>
void allout(std::map<int, std::set<int>> x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << (*it).first << "\n";
        allout((*it).second);
    }
}
template<>
void allout(std::vector<std::vector<int>> x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        allout(*it);
    }
}
template<>
void allout(std::vector<std::string> x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << *it << "\n";
    }
}

#endif

結果

問題	点数	言語	結果	実行時間	メモリ
A. Replace() は Replace() されました	148092974	C++ (gcc)	AC	2934 ms	4316 KiB

テストセット

テストセット	結果	得点	実行時間	メモリ
test_01	AC × 1	3837953	-1 ms	-1 KiB
test_02	AC × 1	4079967	-1 ms	-1 KiB
test_03	AC × 1	3032328	-1 ms	-1 KiB
test_04	AC × 1	941149	-1 ms	-1 KiB
test_05	AC × 1	2496801	-1 ms	-1 KiB
test_06	AC × 1	3179802	-1 ms	-1 KiB
test_07	AC × 1	3515625	-1 ms	-1 KiB
test_08	AC × 1	1064550	-1 ms	-1 KiB
test_09	AC × 1	1330183	-1 ms	-1 KiB
test_10	AC × 1	1172124	-1 ms	-1 KiB
test_11	AC × 1	1988159	-1 ms	-1 KiB
test_12	AC × 1	2773853	-1 ms	-1 KiB
test_13	AC × 1	3084523	-1 ms	-1 KiB
test_14	AC × 1	1333802	-1 ms	-1 KiB
test_15	AC × 1	1577695	-1 ms	-1 KiB
test_16	AC × 1	3598424	-1 ms	-1 KiB
test_17	AC × 1	1550575	-1 ms	-1 KiB
test_18	AC × 1	1075578	-1 ms	-1 KiB
test_19	AC × 1	1207183	-1 ms	-1 KiB
test_20	AC × 1	3681788	-1 ms	-1 KiB

詳細結果

テストケース	結果	実行時間	メモリ
test_01.txt	AC	2909 ms	3964 KiB
test_02.txt	AC	2915 ms	4048 KiB
test_03.txt	AC	2910 ms	3956 KiB
test_04.txt	AC	2913 ms	4308 KiB
test_05.txt	AC	2908 ms	4044 KiB
test_06.txt	AC	2908 ms	4028 KiB
test_07.txt	AC	2910 ms	4220 KiB
test_08.txt	AC	2912 ms	4136 KiB
test_09.txt	AC	2934 ms	4128 KiB
test_10.txt	AC	2909 ms	4116 KiB
test_11.txt	AC	2910 ms	4092 KiB
test_12.txt	AC	2909 ms	4060 KiB
test_13.txt	AC	2909 ms	4000 KiB
test_14.txt	AC	2911 ms	4304 KiB
test_15.txt	AC	2918 ms	4092 KiB
test_16.txt	AC	2906 ms	4084 KiB
test_17.txt	AC	2910 ms	4296 KiB
test_18.txt	AC	2924 ms	4104 KiB
test_19.txt	AC	2911 ms	4316 KiB
test_20.txt	AC	2908 ms	4012 KiB