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 |
|
|
|
|
|
|
|
|
|
|
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 |