Submission #73654620

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>

struct masu_s {
	int y, x, max;
};

int cmp(const void* x, const void* y) {
	struct masu_s a = *(const struct masu_s*)x, b = *(const struct masu_s*)y;
	return
		((a.max > b.max) - (a.max < b.max)) * 4 +
		((a.y > b.y) - (a.y < b.y)) * 2 +
		((a.x > b.x) - (a.x < b.x));
}

int N, M;
int X[212345];
int Y[212345];

int pos_row[212345], gen_row[212345];
int pos_col[212345], gen_col[212345];

int ans[212345], ans_gen[212345];

struct masu_s masu[212345];

int main(void) {
	int T, tc;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 1; tc <= T; tc++) {
		int i, j;
		int masu_cnt;
		if (scanf("%d%d", &N, &M) != 2) return 1;
		for (i = 0; i < N; i++) {
			if (scanf("%d", &X[i]) != 1) return 1;
		}
		for (i = 0; i < M; i++) {
			if (scanf("%d", &Y[i]) != 1) return 1;
		}
		for (i = 0; i < N; i++) {
			if (gen_row[X[i]] == tc) {
				i = -9999;
				break;
			}
			pos_row[X[i]] = i;
			gen_row[X[i]] = tc;
		}
		for (j = 0; j < M; j++) {
			if (gen_col[Y[j]] == tc) {
				j = -9999;
				break;
			}
			pos_col[Y[j]] = j;
			gen_col[Y[j]] = tc;
		}
		/* 1 */
		if (i < 0 || j < 0) {
			puts("No");
			continue;
		}
		/* N * M が無い → 失格 */
		if (gen_row[N * M] != tc || gen_col[N * M] != tc) {
			puts("No");
			continue;
		}
		/* 2 */
		for (i = 1; i <= N * M; i++) {
			if (gen_row[i] == tc && gen_col[i] == tc) {
				int p = pos_row[i] * M + pos_col[i];
				ans[p] = i;
				ans_gen[p] = tc;
			}
		}
		/* 3 */
		for (i = 0; i < N; i++) {
			if (gen_col[X[i]] != tc) { /* この行と同じ最大値を指定する列が無い */
				int p = i * M + pos_col[N * M];
				ans[p] = X[i];
				ans_gen[p] = tc;
			}
		}
		for (i = 0; i < M; i++) {
			if (gen_row[Y[i]] != tc) { /* この列と同じ最大値を指定する行が無い */
				int p = pos_row[N * M] * M + i;
				ans[p] = Y[i];
				ans_gen[p] = tc;
			}
		}
		/* 4 */
		masu_cnt = 0;
		for (i = 0; i < N; i++) {
			for (j = 0; j < M; j++) {
				if (ans_gen[i * M + j] != tc) {
					masu[masu_cnt++] = (struct masu_s){
						i, j, X[i] <= Y[j] ? X[i] : Y[j]
					};
				}
			}
		}
		qsort(masu, masu_cnt, sizeof(*masu), cmp);
		for (i = 1, j = 0; i <= N * M; i++) {
			if (gen_row[i] != tc && gen_col[i] != tc) {
				if (j < masu_cnt && i <= masu[j].max) {
					int p = masu[j].y * M + masu[j].x;
					ans[p] = i;
					ans_gen[p] = tc;
					j++;
				} else {
					break;
				}
			}
		}
		if (i <= N * M || j < masu_cnt) {
			/* 数を入れきれなかった or 余ったマスがある → 失格 */
			puts("No");
		} else {
			puts("Yes");
			for (i = 0; i < N; i++) {
				for (j = 0; j < M; j++) {
					printf(" %d" + !j, ans[i * M + j]);
				}
				putchar('\n');
			}
		}
	}
	return 0;
}

/*

各行/列に、指定の最大値と同じ値の要素が必ず存在する
それがクロスした → 必ずそこに入れる

1. 同じ最大値の指定が同じ方向に複数あれば、No を出力して終わり
2. 同じ最大値の指定がクロスした所を埋める
3. 残りの最大値を、最大値の指定が最大のところに入れる
4. 残りの値を、最大値のminが小さい順に入れる

最大値の指定が最大のところが被ったらどうする？

  4 6 8
3     3
5     5
9     9

うーん……よく考えたら最大値の指定が最大のところって全部同じやねん
詰んでしまったぞ

  4 6 8
3      
5     8
9   6 9

よく考えたら、このケースは無理だぞ (どの列にも9を入れられないので)

  4 6 9
3     3
5     5
9 4 6 9

「クリアできるならば必ずあるはずの、最大値を配置した行/列に他の行/列の最大値を全て置く」
という意味になった
これなら進められそう

でも、これってもったいなくないか？
「選択肢が多い所に入れる」ってしたけど、
それは「せっかく強いのに弱いのを倒すのに消費しちゃう」ことにならないか？

とはいえ、どけたところでそこには結局どけた値未満しか入れられない
別の方向の最大値指定のほうが小さければ、そこには入れられない
よって、入れられるところにはどこに入れてもあまり不利にならなそう？

*/

Submission Info

Judge Result