結果

提出番号	1363
提出者	E869120
言語	C++
提出日時	2018-07-20 17:01:36
問題名	(65)Small Grid and Score
結果	WA
点数	8%

---

テストケース

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;

int Rand(int p, int q) {
	int s = 0, t = 1;
	for (int i = 0; i < 3; i++) { s += (rand() % 1024)*t; t *= 1024; }
	return p + s % (q - p + 1);
}

long long dp[44][44], dp2[44][44], dpr[44][44];

pair<vector<string>, long long> solve(long long N, int ty) {
	for (int i = 0; i < 44; i++) {
		for (int j = 0; j < 44; j++) {
			if (i == 0 || j == 0) dpr[i][j] = 1;
			else dpr[i][j] = dpr[i - 1][j] + dpr[i][j - 1];
		}
	}
	for (int i = 2; i < 44; i++) {
		long long H = i / 2, W = (i + 1) / 2;

		for (int j = 1; j <= 500; j++) {
			vector<string>F(H, "");
			for (int j = 0; j < H; j++) { for (int k = 0; k < W; k++) F[j] += "."; }

			long long S = Rand(H * W / 2, H * W * 7 / 8 + 1);
			for (int k = 1; k <= S; k++) {
				while (true) {
					int px = Rand(0, H - 1), py = Rand(0, W - 1); if (px <= 3 && py >= 16 && Rand(0, 1) == 1) continue;
					if (F[px][py] == '.') { F[px][py] = '2'; break; }
				}
			}
			bool OK = false; dp[0][0] = 1; if (F[0][0] == '2') dp[0][0] = 2;
			for (int k = 0; k < H; k++) {
				for (int l = 0; l < W; l++) {
					if (k == 0 && l == 0) continue;
					dp[k][l] = 0;
					if (k >= 1) dp[k][l] += dp[k - 1][l];
					if (l >= 1) dp[k][l] += dp[k][l - 1];
					if (F[k][l] == '2') dp[k][l] *= 2;
					if (dp[k][l] > N) { OK = true; break; }
				}
			}
			if (OK == true || !(N * 5 / 6 <= dp[H - 1][W - 1] && dp[H - 1][W - 1] <= N)) continue;

			dp2[H - 1][W - 1] = 1; if (F[H - 1][W - 1] == '2') dp2[H - 1][W - 1] = 2;
			for (int k = H - 1; k >= 0; k--) {
				for (int l = W - 1; l >= 0; l--) {
					if (k == H - 1 && l == W - 1) continue;
					dp2[k][l] = 0;
					if (k < H - 1) dp2[k][l] += dp2[k + 1][l];
					if (l < W - 1) dp2[k][l] += dp2[k][l + 1];
					if (F[k][l] == '2') dp2[k][l] *= 2;
				}
			}
			long long A = N - dp[H - 1][W - 1];
			vector<tuple<long long, int, int>>vec;
			for (int k = 0; k < H; k++) {
				for (int l = 0; l < W; l++) { if (F[k][l] == '.') vec.push_back(make_tuple(dpr[k][l] * dp2[k][l], k, l)); }
			}
			sort(vec.begin(), vec.end()); reverse(vec.begin(), vec.end());
			for (int k = 0; k < vec.size(); k++) {
				if (A >= get<0>(vec[k])) { F[get<1>(vec[k])][get<2>(vec[k])] = '1'; A -= get<0>(vec[k]); }
			}
			long long SS = 0, V = A; if (ty >= 1) V *= 2; if (ty == 2) V++;
			while (A >= 2) { if (A % 2 == 1) SS++; A /= 2; SS++; }
			if (SS <= (H + W + 1)) {
				return make_pair(F, V);
			}
		}
	}
	return make_pair(vector<string>{""}, -1);
}

char c[60][60];

void getans(long long N) {
	for (int i = 0; i < 60; i++) { for (int j = 0; j < 60; j++) c[i][j] = '#'; }

	pair<vector<string>, int>C;
	if (N >= (1LL << 58)) {
		if (N % 2 == 0) C = solve(N / 2, 1);
		else C = solve(N / 2, 2);
	}
	else {
		C = solve(N, 0);
	}

	int H = C.first.size(), W = C.first[0].size();
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) { c[i][j + 2] = C.first[i][j]; }
	}
	for (int i = 0; i < H + 2; i++) c[i][0] = '.'; c[0][1] = '.'; if (N >= (1LL << 58)) c[0][1] = '2'; c[H][W + 1] = '.';
	for (int i = 0; i < W + 2; i++) c[H + 1][i] = '.';

	vector<int>G; long long V = C.second;
	while (V >= 2) { if (V % 2 == 1) { G.push_back(1); V--; } G.push_back(2); V /= 2; }
	reverse(G.begin(), G.end());

	if (V == 0) { c[1][0] = '#'; }

	int cx = 1, cy = 0;
	for (int i = 0; i < G.size(); i++) { c[cx][cy] = ('0' + G[i]); if (cx < H + 1) cx++; else cy++; }

	cout << H + 2 << " " << W + 2 << endl;
	for (int i = 0; i < H + 2; i++) {
		for (int j = 0; j < W + 2; j++) cout << c[i][j]; cout << endl;
	}
}

int main() {
	long long n; cin >> n;
	if (n == 0) {
		cout << "1 1" << endl;
		cout << "#" << endl;
		return 0;
	}
	getans(n);
	return 0;
}