Submission #72976579

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
/* 範囲1にset、範囲sum */
#define KI_MAX 128
int ki[KI_MAX * 2 - 1][KI_MAX * 2 - 1];
char ki_all[KI_MAX * 2 - 1][KI_MAX * 2 - 1];
int ki_set_i(
  int iy, int ix,
  int ssx, int ssy, int sdx, int sdy,
  int qsx, int qsy, int qdx, int qdy
) {
  if (qsx <= ssx && sdx <= qdx && qsy <= ssy && sdy <= qdy) {
    /* セグメントがクエリに完全に含まれる */
    ki_all[iy][ix] = 1;
  } else if (sdx <= qsx || qdx <= ssx || sdy <= qsy || qdy <= ssy) {
    /* 完全に外れている */
    /* 何もしない */
  } else if (!ki_all[iy][ix]) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

/* 範囲1にset、範囲sum */

#define KI_MAX 128

int ki[KI_MAX * 2 - 1][KI_MAX * 2 - 1];
char ki_all[KI_MAX * 2 - 1][KI_MAX * 2 - 1];

int ki_set_i(
	int iy, int ix,
	int ssx, int ssy, int sdx, int sdy,
	int qsx, int qsy, int qdx, int qdy
) {
	if (qsx <= ssx && sdx <= qdx && qsy <= ssy && sdy <= qdy) {
		/* セグメントがクエリに完全に含まれる */
		ki_all[iy][ix] = 1;
	} else if (sdx <= qsx || qdx <= ssx || sdy <= qsy || qdy <= ssy) {
		/* 完全に外れている */
		/* 何もしない */
	} else if (!ki_all[iy][ix]) {
		/* 既に全部1の場合は、今回は1に設定するだけなので、変化しない */
		int smx = ssx + (sdx - ssx) / 2;
		int smy = ssy + (sdy - ssy) / 2;
		int c11 = ki_set_i(iy * 2 + 1, ix * 2 + 1, ssx, ssy, smx, smy, qsx, qsy, qdx, qdy);
		int c12 = ki_set_i(iy * 2 + 1, ix * 2 + 2, smx, ssy, sdx, smy, qsx, qsy, qdx, qdy);
		int c21 = ki_set_i(iy * 2 + 2, ix * 2 + 1, ssx, smy, smx, sdy, qsx, qsy, qdx, qdy);
		int c22 = ki_set_i(iy * 2 + 2, ix * 2 + 2, smx, smy, sdx, sdy, qsx, qsy, qdx, qdy);
		ki[iy][ix] = c11 + c12 + c21 + c22;
	}
	if (ki_all[iy][ix]) {
		return (sdx - ssx) * (sdy - ssy);
	} else {
		return ki[iy][ix];
	}
}

void ki_set(int qsx, int qsy, int qdx, int qdy) {
	ki_set_i(0, 0, 0, 0, KI_MAX, KI_MAX, qsx, qsy, qdx, qdy);
}

int ki_get_i(
	int iy, int ix,
	int ssx, int ssy, int sdx, int sdy,
	int qsx, int qsy, int qdx, int qdy
) {
	if (ki_all[iy][ix]) {
		/* 全範囲を1に設定済 */
		int sx = ssx < qsx ? qsx : ssx;
		int sy = ssy < qsy ? qsy : ssy;
		int dx = sdx < qdx ? sdx : qdx;
		int dy = sdy < qdy ? sdy : qdy;
		if (sx > dx || sy > dy) return 0;
		return (dx - sx) * (dy - sy);
	} else if (qsx <= ssx && sdx <= qdx && qsy <= ssy && sdy <= qdy) {
		/* セグメントがクエリに完全に含まれる */
		return ki[iy][ix];
	} else if (sdx <= qsx || qdx <= ssx || sdy <= qsy || qdy <= ssy) {
		/* 完全に外れている */
		return 0;
	} else {
		int smx = ssx + (sdx - ssx) / 2;
		int smy = ssy + (sdy - ssy) / 2;
		int c11 = ki_get_i(iy * 2 + 1, ix * 2 + 1, ssx, ssy, smx, smy, qsx, qsy, qdx, qdy);
		int c12 = ki_get_i(iy * 2 + 1, ix * 2 + 2, smx, ssy, sdx, smy, qsx, qsy, qdx, qdy);
		int c21 = ki_get_i(iy * 2 + 2, ix * 2 + 1, ssx, smy, smx, sdy, qsx, qsy, qdx, qdy);
		int c22 = ki_get_i(iy * 2 + 2, ix * 2 + 2, smx, smy, sdx, sdy, qsx, qsy, qdx, qdy);
		return c11 + c12 + c21 + c22;
	}
}

int ki_get(int qsx, int qsy, int qdx, int qdy) {
	return ki_get_i(0, 0, 0, 0, KI_MAX, KI_MAX, qsx, qsy, qdx, qdy);
}

int N, W, H;
int C[128][128];

int minx[1024], miny[1024], maxx[1024], maxy[1024], count[1024];
int size[1024];
char used[1024];
int ans[1024];

int main(void) {
	int i, j;
	int mieteru_num = 0;
	if (scanf("%d%d%d", &N, &W, &H) != 3) return 1;
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			if (scanf("%d", &C[i][j]) != 1) return 1;
		}
	}

	/* それぞれの色の範囲と個数を調査する */
	for (i = 0; i <= N; i++) {
		minx[i] = W + 1;
		miny[i] = H + 1;
		maxx[i] = -1;
		maxy[i] = -1;
		count[i] = 0;
	}
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			int c = C[i][j];
			if (miny[c] > i) miny[c] = i;
			if (minx[c] > j) minx[c] = j;
			if (maxy[c] < i) maxy[c] = i;
			if (maxx[c] < j) maxx[c] = j;
			count[c]++;
		}
	}
	for (i = 1; i <= N; i++) {
		size[i] = count[i] == 0 ? W * H + 1 : (maxx[i] - minx[i] + 1) * (maxy[i] - miny[i] + 1);
		if (count[i] > 0) mieteru_num++;
	}
	/* 見えている色を取っていく */
	for (i = 0; i < mieteru_num; i++) {
		for (j = 1; j <= N; j++) {
			if (!used[j] && count[j] > 0) {
				if (count[j] + ki_get(minx[j], miny[j], maxx[j] + 1, maxy[j] + 1) == size[j]) {
					ans[i] = j;
					ki_set(minx[j], miny[j], maxx[j] + 1, maxy[j] + 1);
					used[j] = 1;
					break;
				}
			}
		}
		if (j > N) {
			printf("ERROR: i = %d, sinchoku dame desu!\n", i);
			return 42;
		}
	}
	/* 見えていない色を並べる */
	for (i = mieteru_num, j = 1; j <= N; j++) {
		if (!used[j]) {
			if (count[j] > 0) {
				printf("ERROR: color %d left!\n", j);
				return 72;
			}
			ans[i++] = j;
		}
	}

	for (i = 0; i < N; i++) {
		printf(" %d" + !i, ans[N - 1 - i]);
	}
	putchar('\n');

	return 0;
}

/*

まだ選んでいない色について、
「最初からその色」と「取り去った後なので、なんでもあり得る」の数を合計し、
その色がありうる最小の範囲全てがその色なら、選べる

*/

Submission Info

Judge Result