Submission #1141849


Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

class PolyominoEnumeration {
public:
	struct Pos {
		int8_t x, y;
		Pos() : x(0), y(0) {}
		Pos(int x, int y) : x(x), y(y) {}
	};

	struct Polyomino {
		vector<Pos> poses;
		int h, w;
	};

	long long enumerate(int n) {
		H = n;
		W = n * 2 - 1;
		que.resize(H * W);
		placed.resize(n);
		blocked.assign(H * W, false);
		outL = outU = n;
		totalCount = 0;
		for (int x = 0; x < n; ++ x)
			blocked[0 * W + x] = true;
		que[0] = Pos(n - 1, 0);
		result.clear();
		dfs(0, 0, 1);
		return totalCount;
	}

private:
	void dfs(int num, int qh, int qt) {
		for (int i = qh; i < qt; ++ i) {
			Pos pos = que[i];
			placed[num] = pos;
			if (outL <= num + 1 && num + 1 <= outU) {
				int minX = INF, minY = INF;
				int maxX = -INF, maxY = -INF;
				rep(k, num + 1) {
					int x = placed[k].x, y = placed[k].y;
					amin(minX, x);
					amin(minY, y);
					amax(maxX, x);
					amax(maxY, y);
				}
				Polyomino r;
				r.poses.resize(num + 1);
				rep(k, num + 1)
					r.poses[k] = Pos(placed[k].x - minX, placed[k].y - minY);
				r.w = maxX + 1 - minX;
				r.h = maxY + 1 - minY;
				result.push_back(r);
				++ totalCount;
			}
			if (num + 1 < outU) {
				int nqt = qt;
				static const int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };
				for (int d = 0; d < 4; ++ d) {
					int yy = pos.y + dy[d], xx = pos.x + dx[d];
					if (yy < 0 || yy >= H || xx < 0 || xx >= W) continue;
					if (blocked[yy * W + xx]) continue;
					que[nqt ++] = Pos(xx, yy);
				}
				for (int k = qt; k < nqt; ++ k)
					blocked[que[k].y * W + que[k].x] = true;
				dfs(num + 1, i + 1, nqt);
				for (int k = qt; k < nqt; ++ k)
					blocked[que[k].y * W + que[k].x] = false;
			}
		}
	}

	int H, W;
	vector<Pos> que;
	vector<Pos> placed;
	vector<bool> blocked;
	int outL, outU;
	long long totalCount;

public:
	vector<Polyomino> result;
};

struct Placement {
	int prod;
	int pi;
	int i, j;
};

int main() {
#if defined(MY_LOCAL_RUN) && 1
	freopen("C:/test/sagyo/A-in-2.txt", "r", stdin);
	freopen("C:/test/sagyo/A-out.txt", "w", stdout);
#endif
	chrono::high_resolution_clock clk;
	int H; int W; int K;
	while (~scanf("%d%d%d", &H, &W, &K)) {
		auto startTime = clk.now();
		vector<vector<int>> board(H, vector<int>(W));
		rep(i, H) {
			char buf[51];
			scanf("%s", buf);
			rep(j, W)
				board[i][j] = buf[j] - '0';
		}
		vector<Placement> placements;
		PolyominoEnumeration pe;
		pe.enumerate(K);
		rep(pi, pe.result.size()) {
			const auto &p = pe.result[pi];
			rer(i, 0, H - p.h) rer(j, 0, W - p.w) {
				int prod = 1;
				rep(k, K)
					prod *= board[i + p.poses[k].y][j + p.poses[k].x];
				if (prod > 0)
					placements.push_back(Placement{ prod, pi, i, j });
			}
		}
		sort(placements.begin(), placements.end(), [](const Placement &a, const Placement &b) {
			return a.prod > b.prod;
		});
		ll bestTotalScore = 0;
		vector<Placement> bestList;
		mt19937 re;
		while(chrono::duration_cast<chrono::milliseconds>(clk.now() - startTime).count() <= 9000) {
			vector<vector<bool>> blocked(H, vector<bool>(W));
			vector<Placement> list;
			ll totalScore = 0;
			for (auto &&place : placements) {
				const auto &p = pe.result[place.pi];
				int i = place.i;
				int j = place.j;
				bool ok = true;
				rep(k, K)
					ok &= !blocked[i + p.poses[k].y][j + p.poses[k].x];
				if (!ok) continue;
				list.push_back(place);
				totalScore += place.prod;
				rep(k, K)
					blocked[i + p.poses[k].y][j + p.poses[k].x] = true;
			}
			//cerr << iter << ": " << totalScore << endl;
			if (bestTotalScore < totalScore) {
				bestTotalScore = totalScore;
				bestList = list;
			}
			for (auto it = placements.begin(); it != placements.end(); ) {
				auto jt = it;
				for (; jt != placements.end() && jt->prod == it->prod; ++ jt);
				shuffle(it, jt, re);
				it = jt;
			}
		}
#ifdef MY_LOCAL_RUN
		cerr << "score = " << bestTotalScore << endl;
#endif
		printf("%d\n", (int)bestList.size());
		for (auto &&placement : bestList) {
			const auto &p = pe.result[placement.pi];
			int i = placement.i;
			int j = placement.j;
			rep(k, K)
				printf("%d %d\n", i + p.poses[k].y + 1, j + p.poses[k].x + 1);
		}
	}
	return 0;
}

Submission Info

Submission Time
Task A - Multiple Pieces
User anta
Language C++14 (GCC 5.4.1)
Score 950122
Code Size 4858 Byte
Status AC
Exec Time 9088 ms
Memory 67936 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:111:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s", buf);
                    ^

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 95893 / 1343058 90215 / 1343058 97808 / 1343058 90528 / 1343058 102663 / 1343058 91800 / 1343058 98628 / 1343058 87617 / 1343058 99139 / 1343058 95831 / 1343058
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 9073 ms 67296 KB
subtask_01_02.txt AC 9050 ms 66656 KB
subtask_01_03.txt AC 9004 ms 66400 KB
subtask_01_04.txt AC 9024 ms 67424 KB
subtask_01_05.txt AC 9069 ms 66656 KB
subtask_01_06.txt AC 9005 ms 67936 KB
subtask_01_07.txt AC 9033 ms 67808 KB
subtask_01_08.txt AC 9032 ms 66912 KB
subtask_01_09.txt AC 9088 ms 66784 KB
subtask_01_10.txt AC 9047 ms 66656 KB