Submission #667905


Source Code Expand

#include <stdio.h>
#include <inttypes.h>

static uint32_t x=UINT32_C(123456789);
static uint32_t y=UINT32_C(362436069);
static uint32_t z=UINT32_C(521288629);
static uint32_t w=UINT32_C(88675123);

/*
void seed(uint32_t a,uint32_t b,uint32_t c,uint32_t d) {
	if((a|b|c|d)==0)return;
	x=a;y=b;z=c;w=d;
}
*/

uint32_t randint(void) {
	uint32_t t;
	t=(x^(x<<11));
	x=y;y=z;z=w;
	w=(w^(w>>19))^(t^(t>>8));
	return w;
}

/* return [0, num) */
uint32_t randint2(uint32_t num) {
	uint32_t reject = UINT32_MAX % num; /* 何個余るか */
	uint32_t value;
	do {
		value = randint();
	} while (value < reject);
	return value % num;
}

#ifndef WIDTH
#define WIDTH 30
#endif
#ifndef HEIGHT
#define HEIGHT 30
#endif

static const int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int board[HEIGHT][WIDTH];

static int evaluate(int y, int x) {
	int i;
	int score = 0, cur;
	for (i = 0; i < 4; i++) {
		int yy = y + d[i][0], xx = x + d[i][1];
		if (0 <= yy && yy < HEIGHT && 0 <= xx && xx < WIDTH && board[yy][xx] == board[y][x] - 1) {
			cur = 1 + evaluate(yy, xx);
			if (score < cur) score = cur;
		}
	}
	return score;
}

int main(void) {
	int i, j;

	for (i = 0; i < HEIGHT; i++) {
		for (j = 0; j < WIDTH; j++) {
			if (scanf("%d", &board[i][j]) != 1) return 1;
		}
	}

/*

* 最大の数を選ぶ
* 選べる方向の中で一番繋がりそうな感じのやつをランダムに選ぶ

*/

	for(;;) {
		int maxlist[HEIGHT * WIDTH][2];
		int candidates[HEIGHT * WIDTH][2];
		int candidatenum, candidatescore;
		int maxscore = 0, maxnum = 0;
		int idx;

		/* 最大の数を探す */
		for (i = 0; i < HEIGHT; i++) {
			for (j = 0; j < WIDTH; j++) {
				if (board[i][j] > maxscore) {
					maxnum = 0;
					maxscore = board[i][j];
				}
				if (board[i][j] == maxscore) {
					maxlist[maxnum][0] = i;
					maxlist[maxnum][1] = j;
					maxnum++;
				}
			}
		}

		/* 適当に選ぶ */
		if (maxscore <= 0) break;
		candidatenum = 0;
		candidatescore = -1;
		for (i = 0; i < maxnum; i++) {
			int score = evaluate(maxlist[i][0], maxlist[i][1]);
			if (score > candidatescore) {
				candidatenum = 0;
				candidatescore = score;
			}
			if (score == candidatescore) {
				candidates[candidatenum][0] = maxlist[i][0];
				candidates[candidatenum][1] = maxlist[i][1];
				candidatenum++;
			}
		}
		idx = randint2(candidatenum);
		candidatenum = 1;
		candidates[0][0] = candidates[idx][0];
		candidates[0][1] = candidates[idx][1];

		/* 選べる間選ぶ */
		while (candidatenum > 0) {
			int y, x;
			idx = randint2(candidatenum);
			y = candidates[idx][0];
			x = candidates[idx][1];
			printf("%d %d\n", y + 1, x + 1);
			board[y][x]--;
			candidatenum = 0;
			candidatescore = -1;
			if (board[y][x] > 0) {
				for (i = 0; i < 4; i++) {
					int yy = y + d[i][0], xx = x + d[i][1];
					if (0 <= yy && yy < HEIGHT && 0 <= xx && xx < WIDTH && board[yy][xx] == board[y][x]) {
						int score = evaluate(yy, xx);
						if (score > candidatescore) {
							candidatenum = 0;
							candidatescore = score;
						}
						if (score == candidatescore) {
							candidates[candidatenum][0] = yy;
							candidates[candidatenum][1] = xx;
							candidatenum++;
						}
					}
				}
			}
		}
	}

	return 0;
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User mikecat
Language C (GCC 5.4.1)
Score 829217
Code Size 3339 Byte
Status AC
Exec Time 150 ms
Memory 384 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 82851 / 100000 83076 / 100000 83184 / 100000 82333 / 100000 82570 / 100000 82495 / 100000 83536 / 100000 82928 / 100000 83224 / 100000 83020 / 100000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
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
Case Name Status Exec Time Memory
subtask_01_01.txt AC 144 ms 384 KB
subtask_01_02.txt AC 141 ms 384 KB
subtask_01_03.txt AC 141 ms 384 KB
subtask_01_04.txt AC 150 ms 384 KB
subtask_01_05.txt AC 147 ms 384 KB
subtask_01_06.txt AC 141 ms 384 KB
subtask_01_07.txt AC 136 ms 384 KB
subtask_01_08.txt AC 143 ms 384 KB
subtask_01_09.txt AC 136 ms 384 KB
subtask_01_10.txt AC 139 ms 384 KB