提出 a08c3f0d-a101-44d7-85c5-f107f2ca72dc

コード

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

#ifdef DEBUG
ifstream ifs("input.txt");
ofstream ofs("output.txt");

#define cin ifs
#define cout ofs
#endif

struct Op
{
	int id, H, W, a, b;
	bool operator<(const Op &rhs) const
	{
		return H * W >= rhs.H * rhs.W;
	}
};

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;
}

constexpr int LIMIT = 100000;

char used[3000];
int out[LIMIT][3], best_out[LIMIT][3];
int out_cur = 0, best_out_sz = 0;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, T;
	if (!(cin >> N >> T))
		return 0;
	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];
	Op ops[3000];
	for (int t = 0; t < T; ++t)
	{
		ops[t].id = t;
		cin >> ops[t].H >> ops[t].W >> ops[t].a >> ops[t].b;
	}
	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;
	fill(used, used + T, 0);
	fill((int *)out, (int *)out + LIMIT * 3, -1);
	fill((int *)best_out, (int *)best_out + LIMIT * 3, -1);

	int best_score = INT_MAX / 3;

	int lg = 0;
	while ((1 << lg) < N)
		++lg;

	while ((double)(clock() - clk) / CLOCKS_PER_SEC < 2.9)
	{
		shuffle(ops, ops + T, rng);
		bool improved = false;
		for (int t = 0; t < T; ++t)
		{
			int id = ops[t].id, H = ops[t].H, W = ops[t].W, a = ops[t].a, b = ops[t].b;
			int uses = 0;
			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[i][j] - (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)
							A[i][j] = b;
					}
				}
				out[out_cur][0] = id;
				out[out_cur][1] = bestX;
				out[out_cur][2] = bestY;
				++out_cur;
				++used[id];
				improved = true;
			}
		}
		if (!improved)
		{
			int current_score = calc_score(A, B) + out_cur;
			if (current_score < best_score)
			{
				best_score = current_score;
				swap(best_out, out);
			}
			A = atmp;
			best_out_sz = out_cur;
			out_cur = 0;
			fill((int *)out, (int *)out + LIMIT * 3, -1);
			fill(used, used + T, 0);
		}
	}
	{
		int current_score = calc_score(A, B);
		if (current_score < best_score)
		{
			best_score = current_score;
			swap(best_out, out);
			best_out_sz = out_cur;
		}
	}

	cout << best_out_sz << '\n';
	for (int i = 0; i < best_out_sz; ++i)
	{
		int id = best_out[i][0], x = best_out[i][1], y = best_out[i][2];
		cout << id << " " << x << " " << y << "\n";
	}
	return 0;
}
結果

問題	点数	言語	結果	実行時間	メモリ
A - Replace() は Replace() されました	109514526	C++	WA	2962 ms	6416 KiB