Submission #1140716

---

Source Code Expand

#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define SZ(X) ((int64_t)((X).size()))
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define intmax (std::numeric_limits<int64_t>::max() / 4)
#define doublemax (std::numeric_limits<double>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);

typedef pair<double, pair<int, int>>P;

int H, W, K;
const int D[5] = { 0,1,0,-1,0 };

pair<int,vector<array<int,2>>> randomsolve(const vector<vector<int>>S, const int seed) {
	auto searched = S;
	rep(i, H)rep(j, W)searched[i][j] = S[i][j] == 0 ? 1 : 0;

	mt19937_64 rnd(4649);
	uniform_real_distribution<double> r(0, 1);
	priority_queue<P>Q;
	rep(i, H)rep(j, W) {
		P x;
		x.first = r(rnd);
		x.second.first = i;
		x.second.second = j;
		Q.push(x);
	}
	int score = 0;
	vector<array<int, 2>>ans;

	while (!Q.empty()) {
		const P x = Q.top();
		Q.pop();
		const int h = x.second.first;
		const int w = x.second.second;
		vector<array<int, 2>>L;
		priority_queue<P>Q2;
		Q2.push(make_pair(1.0, make_pair(h, w)));
		while ((!Q2.empty()) && int(L.size()) < K) {
			const P x2 = Q2.top();
			Q2.pop();
			const int h2 = x2.second.first;
			const int w2 = x2.second.second;
			if (searched[h2][w2]++)continue;
			L.push_back({ h2,w2 });
			rep(i, 4) {
				const int h3 = h2 + D[i];
				const int w3 = w2 + D[i + 1];
				if (!(0 <= h3&&h3 < H && 0 <= w3&&w3 < W))continue;
				Q2.push(make_pair(r(rnd), make_pair(h3, w3)));
			}
		}
		if (L.size() == K) {
			int s = 1;
			rep(i, K) {
				ans.push_back({ L[i][0] + 1,L[i][1] + 1 });
				s *= S[L[i][0]][L[i][1]];
			}
			score += s;
		}
	}
	return make_pair(score, ans);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> H >> W >> K;
	vector<vector<int>>S(H, vector<int>(W, 0));
	rep(i, H) {
		string a;
		cin >> a;
		assert(a.size() == W);
		rep(j, W)S[i][j] = a[j] - '0';
	}
	auto a = randomsolve(S, 99999999);
	auto score = a.first;
	auto ans = a.second;
	rep(i, 100) {
		auto b = randomsolve(S, i);
		auto newscore = b.first;
		if (score < newscore) {
			score = newscore;
			ans = b.second;
		}
	}
	cout << (ans.size() / K) << endl;
	rep(i, ans.size())cout << ans[i][0] << " " << ans[i][1] << endl;

	return 0;
}

Submission Info

Judge Result