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
2017-03-21 07:17:10+0900
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
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