提出 #17072436

ソースコード 拡げる

Copy
Copy
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define KI_MAX (128 * 128)
  6.  
  7. int ki[KI_MAX];
  8.  
  9. void ki_init(void) {
  10. 	int i;
  11. 	for (i = 0; i < KI_MAX; i++) ki[i] = -1;
  12. }
  13.  
  14. int ki_root(int n) {
  15. #if 0
  16. 	if (ki[n] < 0) return n;
  17. 	return ki[n] = ki_root(ki[n]);
  18. #else
  19. 	static int ki_root_buffer[KI_MAX];
  20. 	int cnt = 0;
  21. 	for (;;) {
  22. 		if (ki[n] < 0) {
  23. 			int i;
  24. 			for (i = 0; i < cnt; i++) ki[ki_root_buffer[i]] = n;
  25. 			return n;
  26. 		} else {
  27. 			ki_root_buffer[cnt++] = n;
  28. 			n = ki[n];
  29. 		}
  30. 	}
  31. #endif
  32. }
  33.  
  34. int ki_size(int n) {
  35. 	return -ki[ki_root(n)];
  36. }
  37.  
  38. void ki_merge(int a, int b) {
  39. 	int ar = ki_root(a);
  40. 	int br = ki_root(b);
  41. 	if (ar != br) {
  42. 		int as = ki_size(ar);
  43. 		int bs = ki_size(br);
  44. 		if (as <= bs) {
  45. 			ki[br] += ki[ar];
  46. 			ki[ar] = br;
  47. 		} else {
  48. 			ki[ar] += ki[br];
  49. 			ki[br] = ar;
  50. 		}
  51. 	}
  52. }
  53.  
  54. /* [(random.randrange(1, 100), random.randrange(1, 100)) for _ in range(85)] */
  55. const int rand_starts[][2] = {
  56. 	{50, 50},
  57. 	{67, 39}, {30, 93}, {65, 81}, { 3, 14}, {21, 57},
  58. 	{72, 29}, {41, 11}, {92, 57}, {68, 35}, {57, 44},
  59. 	{21, 69}, {76, 12}, {85, 89}, { 9, 44}, {98, 90},
  60. 	{ 8, 90}, { 5, 29}, { 7,  1}, {47, 58}, {35, 82},
  61. 	{66, 30}, {22, 62}, {79, 58}, {73, 97}, {96, 73},
  62. 	{98, 90}, {72, 32}, {10, 37}, {73, 81}, {86, 64},
  63. 	{44, 56}, {21, 86}, {42, 49}, {44, 39}, {46, 54},
  64. 	{85, 53}, {78, 78}, {15,  9}, { 6, 93}, {77, 95},
  65. 	{ 9, 28}, {87, 30}, {13, 14}, {86, 87}, {37, 46},
  66. 	{28, 55}, {19, 47}, {27, 40}, {29, 74}, {60, 82},
  67. 	{45, 88}, { 9,  8}, {54, 70}, {47, 13}, {81, 42},
  68. 	{60, 26}, {98, 29}, {68, 84}, {70, 17}, {83,  5},
  69. 	{98, 40}, {97, 48}, {51, 96}, {69, 52}, {15, 41},
  70. 	{76,  1}, {82, 64}, {19, 93}, {58, 63}, {32, 93},
  71. 	{53,  3}, {43, 23}, { 3, 74}, {15, 85}, {41, 37},
  72. 	{24, 71}, {16, 28}, {30, 79}, {65, 80}, {11, 67},
  73. 	{ 1,  5}, {51, 19}, {61, 90}, {70, 21}, {67,  2}
  74. };
  75.  
  76. int ki_initial[KI_MAX];
  77.  
  78. int id, N, K;
  79. char S[128][128];
  80.  
  81. int ki_id(int y, int x) {
  82. 	return y * 128 + x;
  83. }
  84.  
  85. int moveCount = 0;
  86. int moves[128 * 128];
  87.  
  88. int done[128][128];
  89.  
  90. int dlist[9][128 * 128][2];
  91.  
  92. int maxMoveCount = 128 * 128;
  93. int maxMoves[128 * 128];
  94. int maxCy, maxCx;
  95.  
  96. int main(void) {
  97. 	int i, j;
  98. 	int cid;
  99. 	int gen;
  100. 	int snum = (int)(sizeof(rand_starts) / sizeof(*rand_starts));
  101. 	int scount;
  102. 	if (scanf("%d%d%d", &id, &N, &K) != 3) return 1;
  103. 	if (N >= (int)(sizeof(S) / sizeof(*S))) {
  104. 		puts("0");
  105. 		return 0;
  106. 	}
  107. 	for (i = 0; i < N; i++) {
  108. 		if (scanf("%127s", S[i]) != 1) return 1;
  109. 	}
  110.  
  111. 	ki_init();
  112. 	for (i = 0; i < N; i++) {
  113. 		for (j = 0; j < N; j++) {
  114. 			if (i + 1 < N && S[i][j] == S[i + 1][j]) ki_merge(ki_id(i, j), ki_id(i + 1, j));
  115. 			if (j + 1 < N && S[i][j] == S[i][j + 1]) ki_merge(ki_id(i, j), ki_id(i, j + 1));
  116. 		}
  117. 	}
  118. 	memcpy(ki_initial, ki, sizeof(ki));
  119.  
  120. 	for (scount = 0; scount < snum; scount++) {
  121. 		int cy = rand_starts[scount][0], cx = rand_starts[scount][1];
  122. 		if (cy > N) cy = (N + 1) / 2;
  123. 		if (cx > N) cx = (N + 1) / 2;
  124. 		cid = ki_id(cy - 1, cx - 1);
  125. 		moveCount =0;
  126. 		memset(done, 0, sizeof(done));
  127. 		memcpy(ki, ki_initial, sizeof(ki));
  128.  
  129. 		for (gen = 1; ki_size(cid) < N * N; gen++) {
  130. 			int score[9] = {0};
  131. 			int dnum[9] = {0};
  132. 			int smax = 0;
  133. 			for (i = 0; i < N; i++) {
  134. 				for (j = 0; j < N; j++) {
  135. 					if (ki_root(cid) == ki_root(ki_id(i, j))) {
  136. 						static const int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  137. 						int k;
  138. 						for (k = 0; k < 4; k++) {
  139. 							int di = d[k][0], dj = d[k][1];
  140. 							if (0 <= i + di && i + di < N && 0 <= j + dj && j + dj < N &&
  141. 							ki_root(cid) != ki_root(ki_id(i + di, j + dj)) && done[i + di][j + dj] < gen) {
  142. 								int sid = S[i + di][j + dj] - '1';
  143. 								score[sid] += ki_size(ki_id(i + di, j + dj));
  144. 								done[i + di][j + dj] = gen;
  145. 								dlist[sid][dnum[sid]][0] = i + di;
  146. 								dlist[sid][dnum[sid]][1] = j + dj;
  147. 								dnum[sid]++;
  148. 							}
  149. 						}
  150. 					}
  151. 				}
  152. 			}
  153. 			for (i = 1; i < K; i++) {
  154. 				if(score[i] > score[smax]) smax = i;
  155. 			}
  156. 			moves[moveCount++] = smax + 1;
  157. 			for (i = 0; i < dnum[smax]; i++) {
  158. 				ki_merge(cid, ki_id(dlist[smax][i][0], dlist[smax][i][1]));
  159. 			}
  160. 		}
  161. 		if (moveCount < maxMoveCount) {
  162. 			maxMoveCount = moveCount;
  163. 			memcpy(maxMoves, moves, sizeof(*moves) * moveCount);
  164. 			maxCy = cy;
  165. 			maxCx = cx;
  166. 		}
  167. 	}
  168.  
  169. 	printf("%d\n", maxMoveCount);
  170. 	for (i = 0; i < maxMoveCount; i++) {
  171. 		printf("%d %d %d\n", maxCy, maxCx, maxMoves[i]);
  172. 	}
  173.  
  174. 	return 0;
  175. }
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define KI_MAX (128 * 128)

int ki[KI_MAX];

void ki_init(void) {
	int i;
	for (i = 0; i < KI_MAX; i++) ki[i] = -1;
}

int ki_root(int n) {
#if 0
	if (ki[n] < 0) return n;
	return ki[n] = ki_root(ki[n]);
#else
	static int ki_root_buffer[KI_MAX];
	int cnt = 0;
	for (;;) {
		if (ki[n] < 0) {
			int i;
			for (i = 0; i < cnt; i++) ki[ki_root_buffer[i]] = n;
			return n;
		} else {
			ki_root_buffer[cnt++] = n;
			n = ki[n];
		}
	}
#endif
}

int ki_size(int n) {
	return -ki[ki_root(n)];
}

void ki_merge(int a, int b) {
	int ar = ki_root(a);
	int br = ki_root(b);
	if (ar != br) {
		int as = ki_size(ar);
		int bs = ki_size(br);
		if (as <= bs) {
			ki[br] += ki[ar];
			ki[ar] = br;
		} else {
			ki[ar] += ki[br];
			ki[br] = ar;
		}
	}
}

/* [(random.randrange(1, 100), random.randrange(1, 100)) for _ in range(85)] */
const int rand_starts[][2] = {
	{50, 50},
	{67, 39}, {30, 93}, {65, 81}, { 3, 14}, {21, 57},
	{72, 29}, {41, 11}, {92, 57}, {68, 35}, {57, 44},
	{21, 69}, {76, 12}, {85, 89}, { 9, 44}, {98, 90},
	{ 8, 90}, { 5, 29}, { 7,  1}, {47, 58}, {35, 82},
	{66, 30}, {22, 62}, {79, 58}, {73, 97}, {96, 73},
	{98, 90}, {72, 32}, {10, 37}, {73, 81}, {86, 64},
	{44, 56}, {21, 86}, {42, 49}, {44, 39}, {46, 54},
	{85, 53}, {78, 78}, {15,  9}, { 6, 93}, {77, 95},
	{ 9, 28}, {87, 30}, {13, 14}, {86, 87}, {37, 46},
	{28, 55}, {19, 47}, {27, 40}, {29, 74}, {60, 82},
	{45, 88}, { 9,  8}, {54, 70}, {47, 13}, {81, 42},
	{60, 26}, {98, 29}, {68, 84}, {70, 17}, {83,  5},
	{98, 40}, {97, 48}, {51, 96}, {69, 52}, {15, 41},
	{76,  1}, {82, 64}, {19, 93}, {58, 63}, {32, 93},
	{53,  3}, {43, 23}, { 3, 74}, {15, 85}, {41, 37},
	{24, 71}, {16, 28}, {30, 79}, {65, 80}, {11, 67},
	{ 1,  5}, {51, 19}, {61, 90}, {70, 21}, {67,  2}
};

int ki_initial[KI_MAX];

int id, N, K;
char S[128][128];

int ki_id(int y, int x) {
	return y * 128 + x;
}

int moveCount = 0;
int moves[128 * 128];

int done[128][128];

int dlist[9][128 * 128][2];

int maxMoveCount = 128 * 128;
int maxMoves[128 * 128];
int maxCy, maxCx;

int main(void) {
	int i, j;
	int cid;
	int gen;
	int snum = (int)(sizeof(rand_starts) / sizeof(*rand_starts));
	int scount;
	if (scanf("%d%d%d", &id, &N, &K) != 3) return 1;
	if (N >= (int)(sizeof(S) / sizeof(*S))) {
		puts("0");
		return 0;
	}
	for (i = 0; i < N; i++) {
		if (scanf("%127s", S[i]) != 1) return 1;
	}

	ki_init();
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (i + 1 < N && S[i][j] == S[i + 1][j]) ki_merge(ki_id(i, j), ki_id(i + 1, j));
			if (j + 1 < N && S[i][j] == S[i][j + 1]) ki_merge(ki_id(i, j), ki_id(i, j + 1));
		}
	}
	memcpy(ki_initial, ki, sizeof(ki));

	for (scount = 0; scount < snum; scount++) {
		int cy = rand_starts[scount][0], cx = rand_starts[scount][1];
		if (cy > N) cy = (N + 1) / 2;
		if (cx > N) cx = (N + 1) / 2;
		cid = ki_id(cy - 1, cx - 1);
		moveCount =0;
		memset(done, 0, sizeof(done));
		memcpy(ki, ki_initial, sizeof(ki));

		for (gen = 1; ki_size(cid) < N * N; gen++) {
			int score[9] = {0};
			int dnum[9] = {0};
			int smax = 0;
			for (i = 0; i < N; i++) {
				for (j = 0; j < N; j++) {
					if (ki_root(cid) == ki_root(ki_id(i, j))) {
						static const int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
						int k;
						for (k = 0; k < 4; k++) {
							int di = d[k][0], dj = d[k][1];
							if (0 <= i + di && i + di < N && 0 <= j + dj && j + dj < N &&
							ki_root(cid) != ki_root(ki_id(i + di, j + dj)) && done[i + di][j + dj] < gen) {
								int sid = S[i + di][j + dj] - '1';
								score[sid] += ki_size(ki_id(i + di, j + dj));
								done[i + di][j + dj] = gen;
								dlist[sid][dnum[sid]][0] = i + di;
								dlist[sid][dnum[sid]][1] = j + dj;
								dnum[sid]++;
							}
						}
					}
				}
			}
			for (i = 1; i < K; i++) {
				if(score[i] > score[smax]) smax = i;
			}
			moves[moveCount++] = smax + 1;
			for (i = 0; i < dnum[smax]; i++) {
				ki_merge(cid, ki_id(dlist[smax][i][0], dlist[smax][i][1]));
			}
		}
		if (moveCount < maxMoveCount) {
			maxMoveCount = moveCount;
			memcpy(maxMoves, moves, sizeof(*moves) * moveCount);
			maxCy = cy;
			maxCx = cx;
		}
	}

	printf("%d\n", maxMoveCount);
	for (i = 0; i < maxMoveCount; i++) {
		printf("%d %d %d\n", maxCy, maxCx, maxMoves[i]);
	}

	return 0;
}

提出情報

提出日時
問題 A - カラフルパネル
ユーザ mikecat
言語 C (GCC 9.2.1)
得点 49990800
コード長 4450 Byte
結果
実行時間 2961 ms
メモリ 1984 KB

ジャッジ結果

セット名 test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10 test_11 test_12 test_13 test_14 test_15 test_16 test_17 test_18 test_19 test_20 test_21 test_22 test_23 test_24 test_25 test_26 test_27 test_28 test_29 test_30 test_31 test_32 test_33 test_34 test_35 test_36 test_37 test_38 test_39 test_40 test_41 test_42 test_43 test_44 test_45 test_46 test_47 test_48 test_49 test_50
得点 / 配点 999816 / 1000000 999815 / 1000000 999817 / 1000000 999809 / 1000000 999821 / 1000000 999818 / 1000000 999818 / 1000000 999823 / 1000000 999820 / 1000000 999815 / 1000000 999819 / 1000000 999811 / 1000000 999822 / 1000000 999813 / 1000000 999822 / 1000000 999809 / 1000000 999818 / 1000000 999818 / 1000000 999815 / 1000000 999821 / 1000000 999814 / 1000000 999814 / 1000000 999808 / 1000000 999817 / 1000000 999813 / 1000000 999815 / 1000000 999819 / 1000000 999811 / 1000000 999811 / 1000000 999812 / 1000000 999812 / 1000000 999824 / 1000000 999815 / 1000000 999825 / 1000000 999811 / 1000000 999825 / 1000000 999823 / 1000000 999816 / 1000000 999803 / 1000000 999816 / 1000000 999814 / 1000000 999813 / 1000000 999812 / 1000000 999821 / 1000000 999817 / 1000000 999823 / 1000000 999804 / 1000000 999819 / 1000000 999826 / 1000000 999807 / 1000000
結果
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
セット名 テストケース
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
test_11 subtask_01_11.txt
test_12 subtask_01_12.txt
test_13 subtask_01_13.txt
test_14 subtask_01_14.txt
test_15 subtask_01_15.txt
test_16 subtask_01_16.txt
test_17 subtask_01_17.txt
test_18 subtask_01_18.txt
test_19 subtask_01_19.txt
test_20 subtask_01_20.txt
test_21 subtask_01_21.txt
test_22 subtask_01_22.txt
test_23 subtask_01_23.txt
test_24 subtask_01_24.txt
test_25 subtask_01_25.txt
test_26 subtask_01_26.txt
test_27 subtask_01_27.txt
test_28 subtask_01_28.txt
test_29 subtask_01_29.txt
test_30 subtask_01_30.txt
test_31 subtask_01_31.txt
test_32 subtask_01_32.txt
test_33 subtask_01_33.txt
test_34 subtask_01_34.txt
test_35 subtask_01_35.txt
test_36 subtask_01_36.txt
test_37 subtask_01_37.txt
test_38 subtask_01_38.txt
test_39 subtask_01_39.txt
test_40 subtask_01_40.txt
test_41 subtask_01_41.txt
test_42 subtask_01_42.txt
test_43 subtask_01_43.txt
test_44 subtask_01_44.txt
test_45 subtask_01_45.txt
test_46 subtask_01_46.txt
test_47 subtask_01_47.txt
test_48 subtask_01_48.txt
test_49 subtask_01_49.txt
test_50 subtask_01_50.txt
ケース名 結果 実行時間 メモリ
subtask_01_01.txt 2825 ms 1912 KB
subtask_01_02.txt 2847 ms 1860 KB
subtask_01_03.txt 2863 ms 1900 KB
subtask_01_04.txt 2835 ms 1968 KB
subtask_01_05.txt 2869 ms 1868 KB
subtask_01_06.txt 2869 ms 1968 KB
subtask_01_07.txt 2856 ms 1936 KB
subtask_01_08.txt 2896 ms 1984 KB
subtask_01_09.txt 2815 ms 1896 KB
subtask_01_10.txt 2847 ms 1904 KB
subtask_01_11.txt 2826 ms 1864 KB
subtask_01_12.txt 2880 ms 1904 KB
subtask_01_13.txt 2830 ms 1976 KB
subtask_01_14.txt 2845 ms 1980 KB
subtask_01_15.txt 2851 ms 1940 KB
subtask_01_16.txt 2906 ms 1864 KB
subtask_01_17.txt 2836 ms 1904 KB
subtask_01_18.txt 2906 ms 1900 KB
subtask_01_19.txt 2828 ms 1912 KB
subtask_01_20.txt 2818 ms 1908 KB
subtask_01_21.txt 2909 ms 1976 KB
subtask_01_22.txt 2901 ms 1976 KB
subtask_01_23.txt 2887 ms 1904 KB
subtask_01_24.txt 2900 ms 1864 KB
subtask_01_25.txt 2880 ms 1900 KB
subtask_01_26.txt 2733 ms 1856 KB
subtask_01_27.txt 2961 ms 1980 KB
subtask_01_28.txt 2847 ms 1868 KB
subtask_01_29.txt 2908 ms 1864 KB
subtask_01_30.txt 2854 ms 1908 KB
subtask_01_31.txt 2862 ms 1980 KB
subtask_01_32.txt 2781 ms 1868 KB
subtask_01_33.txt 2848 ms 1900 KB
subtask_01_34.txt 2818 ms 1904 KB
subtask_01_35.txt 2845 ms 1976 KB
subtask_01_36.txt 2815 ms 1904 KB
subtask_01_37.txt 2835 ms 1912 KB
subtask_01_38.txt 2901 ms 1860 KB
subtask_01_39.txt 2945 ms 1860 KB
subtask_01_40.txt 2884 ms 1860 KB
subtask_01_41.txt 2874 ms 1908 KB
subtask_01_42.txt 2890 ms 1900 KB
subtask_01_43.txt 2888 ms 1980 KB
subtask_01_44.txt 2813 ms 1864 KB
subtask_01_45.txt 2860 ms 1904 KB
subtask_01_46.txt 2870 ms 1908 KB
subtask_01_47.txt 2833 ms 1860 KB
subtask_01_48.txt 2829 ms 1864 KB
subtask_01_49.txt 2961 ms 1860 KB
subtask_01_50.txt 2942 ms 1936 KB
Facebook Twitter Hatena Share

2020-09-27 (日)
14:34:30 +00:00