Submission #1226322


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;

typedef long long ll;

#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 };

double temperature(double start, double end, double r);
double probability(double e1, double e2, double t);
void gen_rand_next_field(const char c_field[N + 5][N + 5], char n_field[N + 5][N + 5]);
ll make_rand();
double gen_per_rand(const ll res = 1LL << 60) {
	return 1.0 * (make_rand() % res) / (res - 1);
}

chrono::system_clock::time_point start;

int main() {

	start = chrono::system_clock::now();

	int i, j;

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

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

	//beam_search();
	SA();

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

	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 > 5) {
								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;
}
double temperature(double start, double end, double r) {
	return start + (end - start) * r;
}

double probability(double e1, double e2, double t) {
	if (e1 <= e2) {
		return 1;
	}
	else {
		double res = exp((-e1 + e2) / t);
		return res;
	}
}
void gen_rand_next_field(const char c_field[N + 5][N + 5], char n_field[N + 5][N + 5]) {

	const int col = make_rand() % N;

	int i, j;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			n_field[i][j] = c_field[i][j];
		}
	}

	for (i = 0; i < N; i++) {
		if (make_rand() % 2 == 0) {
			if (OK[i][col] == 1) {
				int n = make_rand() % 100;
				if (n <= 85){
					n_field[i][col] = '.';
				}
				else if (n <= 98){
					n_field[i][col] = '+';
				}
				else{
					n_field[i][col] = '-';
				}
			}
		}
	}

}
ll make_rand() {
	static ll x = 123456789;
	static ll y = 362436069;
	static ll z = 521288629;
	static ll w = 88675123;
	ll t;
	t = x ^ (x << 11);
	x = y; y = z; z = w;
	return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
void SA() {

	time_t stime = time(NULL);

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

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

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

	fall();

	char c_field[N + 5][N + 5];
	memcpy(c_field, ans, sizeof(ans));
	int c_score = calc_score();


	char b_field[N + 5][N + 5];
	memcpy(b_field, c_field, sizeof(c_field));
	int b_score = c_score;

	double param1, param2;

	double diff = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() / 1000.;

	double simulate_time = (9.99 - diff)*1000.0;

	param1 = 1.0 / (simulate_time / 4.8);
	param2 = 1.0 / exp(4.8);

	while (1) {

		diff = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() / 1000.;
		if (diff > 9.99) {
			break;
		}

		char n_field[N + 5][N + 5];
		gen_rand_next_field(c_field, n_field);
		memcpy(S, n_field, sizeof(n_field));
		fall();
		int n_score = calc_score();

		if (n_score > b_score) {
			memcpy(b_field, n_field, sizeof(b_field));
			b_score = n_score;
		}

		if (gen_per_rand() <= probability(c_score, n_score, 25.0 * exp((9.99 - diff) * param1*1000.0) * param2)) {
			memcpy(c_field, n_field, sizeof(n_field));
			c_score = n_score;
		}
	}

	//cout << "best_score : " << b_score << endl;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << b_field[i][j];
		}
		cout << endl;
	}


}

Submission Info

Submission Time
Task A - ○×ブロック
User tekitouk
Language C++14 (GCC 5.4.1)
Score 7149
Code Size 6769 Byte
Status AC
Exec Time 9992 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:68:20: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[55]’ [-Wformat=]
   scanf("%s", &S[i]);
                    ^
./Main.cpp:68: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 660 / 2500 759 / 2500 657 / 2500 763 / 2500 733 / 2500 702 / 2500 746 / 2500 702 / 2500 706 / 2500 721 / 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 9992 ms 256 KB
subtask_01_02.txt AC 9992 ms 256 KB
subtask_01_03.txt AC 9992 ms 256 KB
subtask_01_04.txt AC 9992 ms 256 KB
subtask_01_05.txt AC 9992 ms 256 KB
subtask_01_06.txt AC 9992 ms 256 KB
subtask_01_07.txt AC 9992 ms 256 KB
subtask_01_08.txt AC 9992 ms 256 KB
subtask_01_09.txt AC 9992 ms 256 KB
subtask_01_10.txt AC 9992 ms 256 KB