結果

問題 No.1123 Afforestation
ユーザー e869120
提出日時 2020-07-03 00:11:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,069 bytes
コンパイル時間 1,174 ms
コンパイル使用メモリ 80,024 KB
実行使用メモリ 9,752 KB
最終ジャッジ日時 2024-09-16 17:04:19
合計ジャッジ時間 14,574 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 66 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

// 入力
int H, A[2509];
int W, B[2509];
int K, X[19], Y[19];

// その他
int Answer[2509][2509];
bool used[2509][2509];
bool forced[2509][2509];

int main() {
	// 入力
	cin >> H >> W;
	for (int i = 1; i <= H; i++) cin >> A[i];
	for (int i = 1; i <= W; i++) cin >> B[i];
	cin >> K;
	for (int i = 1; i <= K; i++) cin >> X[i] >> Y[i];

	// 貪欲法
	vector<pair<int, int>> CA, CB;
	for (int i = 1; i <= K; i++) forced[X[i]][Y[i]] = true;
	for (int i = 1; i <= H; i++) CA.push_back(make_pair(A[i], i));
	for (int i = 1; i <= W; i++) CB.push_back(make_pair(B[i], i));
	sort(CA.begin(), CA.end()); reverse(CA.begin(), CA.end());
	sort(CB.begin(), CB.end()); reverse(CB.begin(), CB.end());
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < CA[i].first; j++) used[CA[i].second][CB[j].second] = true;
		for (int j = 0; j < CA[i].first; j++) CB[j].first -= 1;
		sort(CB.begin(), CB.end()); reverse(CB.begin(), CB.end());
	}
	if (CB[0].first >= 1) {
		printf(":(\n");
		return 0;
	}

	// 判定
	int SA = 0; for (int i = 1; i <= H; i++) SA += A[i];
	int SB = 0; for (int i = 1; i <= W; i++) SB += B[i];
	if (SA != SB) {
		printf(":(\n");
		return 0;
	}

	// 書き換え
	for (int i = 1; i <= K; i++) {
		if (used[X[i]][Y[i]] == false) continue;
		bool flag = false;
		for (int j = 1; j <= H; j++) {
			for (int k = 1; k <= W; k++) {
				if (used[X[i]][k] == true || forced[X[i]][k] == true) continue;
				if (used[j][Y[i]] == true || forced[j][Y[i]] == true) continue;
				if (used[j][k] == false) continue;
				flag = true;
				used[X[i]][k] = true;
				used[j][Y[i]] = true;
				used[j][k] = false;
				break;
			}
			if (flag == true) break;
		}
		if (flag == false) {
			cout << ":(" << endl;
			return 0;
		}
	}

	// 出力
	printf("Yay!\n");
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (forced[i][j] == true) printf("x");
			else if (used[i][j] == true) printf("o");
			else printf(".");
		}
		printf("\n");
	}
	return 0;
}
0