Submission #1175063


Source Code Expand

#include <vector>
#include <cfloat>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <string>
#include <iostream>
#include <cstdint>
#include <algorithm>
#include <cassert>
#include <random>
#include <queue>
#include <list>
#include <map>
#include <array>
#include <chrono>

using namespace std;


#define N 50
#define beam_width 5

char S[N + 5][N + 5];
char ans[N + 5][N + 5];
char dummy[N + 5][N + 5];
int OK[N + 5][N + 5] = { 0 };

void fall();
int calc_score();
void beam_search();
int rank_check(int play);
void SA();

template<typename T>
using Board = array<array<T, N + 2>, N + 2>;

int dfs(int y, int x, Board<bool> &visited, const char ch);

struct data {
	int score;
	char state[N + 5][N + 5];
}node[beam_width], temp, dum[beam_width];

array<int, 4> dxs = { 0, 1, 0, -1 };
array<int, 4> dys = { 1, 0, -1, 0 };

int main() {

	int i, j;

	for (i = 0; i < N; i++) {
		scanf("%s", &S[i]);
	}

	beam_search();
	SA();

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			printf("%c", ans[i][j]);
		}
		printf("\n");
	}


	//cout << time(NULL) - stime << endl;

	return 0;
}
int dfs(int y, int x, Board<bool> &visited, const char ch)
{
	int ans = 1;
	visited[y][x] = true;
	for (int i = 0; i < 4; i++)
	{
		const int ny = y + dys[i];
		const int nx = x + dxs[i];
		if (0 <= ny&&ny < N && 0 <= nx&&nx < N) {
			if (!visited[ny][nx] && S[ny][nx] == ch)
			{
				ans += dfs(ny, nx, visited, ch);
			}
		}
	}
	return ans;
}
void fall() {
	int i, j;
	for (j = 0; j < N; j++) {
		int tgt = N - 1;
		for (i = N - 1; i >= 0; i--) {
			if (S[i][j] == '-') {
				tgt = i - 1;
			}
			else if (S[i][j] != '.') {
				char c = S[i][j];
				S[i][j] = '.';
				S[tgt][j] = c;
				tgt--;
			}
		}
	}
}


int calc_score() {
	Board<bool> visited;
	for (auto &ary : visited)
	{
		fill(ary.begin(), ary.end(), false);
	}
	int score_x = 0;
	int score_o = 0;
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			if (!visited[y][x])
			{
				if (S[y][x] == 'o')
				{
					score_o = max(score_o, dfs(y, x, visited, 'o'));
				}
				if (S[y][x] == 'x')
				{
					score_x = max(score_x, dfs(y, x, visited, 'x'));
				}
			}
		}
	}

	return score_x + score_o;
}
void beam_search() {

	int i, j, k, m;

	for (i = 0; i < beam_width; i++) {
		node[i].score = 0;
		memcpy(node[i].state, S, sizeof(S));
	}
	int size = 1;

	char c[3] = { '.','+','-' };

	int rank, dumsize;

	time_t stime = time(NULL);

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (S[i][j] == '.') { OK[i][j] = 1; }
		}
	}

	while (1) {
		for (i = N - 1; i >= 0; i--) {
			for (j = N - 1; j >= 0; j--) {
				dumsize = 0;
				if (OK[i][j] == 1) {
					for (k = 0; k < size; k++) {
						for (m = 0; m < 3; m++) {
							if (time(NULL) - stime > 6) {
								int best = -(1 << 30);
								int index;
								int a;
								for (a = 0; a < beam_width; a++) {
									if (best < node[a].score) {
										best = node[a].score;
										index = a;
									}
								}
								memcpy(ans, node[index].state, sizeof(node[index].state));
								return;
							}
							temp = node[k];
							temp.state[i][j] = c[m];
							memcpy(S, temp.state, sizeof(temp.state));
							fall();
							temp.score = calc_score();
							if (dumsize < beam_width) {
								dum[dumsize] = temp;
								dumsize++;
							}
							else if (dumsize == beam_width) {
								rank = rank_check(beam_width);
								if (temp.score > dum[rank].score) {
									dum[rank] = temp;
								}
							}
						}
					}
				}
				else { continue; }
				for (k = 0; k < dumsize; k++) {
					node[k] = dum[k];
				}
				size = dumsize;
			}
		}
	}

}
int rank_check(int play) {

	int i;
	int worst = (1 << 30);
	int index;
	for (i = 0; i<play; i++) {
		if (worst>dum[i].score) {
			worst = dum[i].score;
			index = i;
		}
	}
	return index;
}
void SA() {

	time_t stime = time(NULL);

	random_device rd;

	mt19937 mt(rd());

	uniform_int_distribution<int> dice1(0, 2);
	uniform_int_distribution<int> dice2(0, N - 1);
	uniform_int_distribution<int> dice3(0, N - 1);

	char c[3] = { '+','-','.' };

	memcpy(S, ans, sizeof(ans));

	fall();

	int before = calc_score();
	int after;

	//printf("before=%d\n",before);

	while (1) {
		memcpy(dummy, ans, sizeof(ans));
		if (time(NULL) - stime > 2) {
			break;
		}
		int cnt = 0;
		while (1) {
			int y = dice2(mt);
			int x = dice3(mt);
			if (OK[y][x] == 1) {
				cnt++;
				dummy[y][x] = c[dice1(mt)];
				if (cnt >= 3) {
					break;
				}
			}
		}
		memcpy(S, dummy, sizeof(dummy));
		fall();
		after = calc_score();
		if (after > before) {
			memcpy(ans, dummy, sizeof(dummy));
			before = after;
		}
	}
	//printf("after=%d\n", before);

}

Submission Info

Submission Time
Task A - ○×ブロック
User tekitouk
Language C++14 (GCC 5.4.1)
Score 5992
Code Size 4955 Byte
Status AC
Exec Time 9551 ms
Memory 384 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:55:20: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[55]’ [-Wformat=]
   scanf("%s", &S[i]);
                    ^
./Main.cpp:55:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &S[i]);
                     ^

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 542 / 2500 647 / 2500 620 / 2500 559 / 2500 711 / 2500 501 / 2500 639 / 2500 553 / 2500 599 / 2500 621 / 2500
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 9175 ms 256 KB
subtask_01_02.txt AC 9539 ms 256 KB
subtask_01_03.txt AC 9551 ms 256 KB
subtask_01_04.txt AC 9531 ms 256 KB
subtask_01_05.txt AC 9543 ms 256 KB
subtask_01_06.txt AC 9531 ms 256 KB
subtask_01_07.txt AC 9539 ms 256 KB
subtask_01_08.txt AC 9531 ms 384 KB
subtask_01_09.txt AC 9535 ms 256 KB
subtask_01_10.txt AC 9543 ms 256 KB