//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright Copyright (c) 2018 HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください。
//------------------------------------------------------------------------------
#include "Answer.hpp"
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define REP(i,n) for(long long i = 0;i < n;++i)
#define seg_size 524288
unsigned long xor128() {
static unsigned long x = time(NULL), y = 362436069, z = 521288629, w = 88675123;
unsigned long t = (x ^ (x << 11));
x = y; y = z; z = w;
return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
//------------------------------------------------------------------------------
namespace hpc {
tuple<int, int, int, int> small_piece[8], large_piece[8]; // width,height,加熱にかかる時間,score
int remaining_turn = 0;
int grid[20][20] = {};
int bad[20][20] = {};
tuple<int, int, int> expected;
//ここから 0-7 -> small_pieceのindex,8-15 -> large_pieceのindex,-1 -> 設置なし
tuple<int, int, int> next() {
for (int i = 0; i < 20; ++i) {
for (int q = 0; q < 20; ++q) {
bad[i][q] = 10000;
}
}
vector<pair<int, int>> winner;
REP(i, 8) {
winner.push_back(make_pair(-1, -1));
}
double now_ans = -1;
double bea = 0;
int loop_cnt = 0;
int failed_cnt = 0;
pair<int, int> go[501][8];
REP(index, 8) {
go[0][index] = make_pair(0, 0);
go[1][index] = make_pair(20 - get<0>(large_piece[index]), 0);
go[2][index] = make_pair(0, 20 - get<1>(large_piece[index]));
go[3][index] = make_pair(20 - get<0>(large_piece[index]), 20 - get<1>(large_piece[index]));
int now_moving = 4;
int failed[20][20] = {};
int donot[20][20] = {};
int xe[4] = { 1,-1,0,0 };
int ye[4] = { 0,0,1,-1 };
for (int tea = 0; tea < (21 - get<0>(large_piece[index]))*(21 - get<1>(large_piece[index])); ++tea) {
pair<int, int> now = go[tea][index];
for (int i = 0; i < 4; ++i) {
int x = now.first + xe[i];
int y = now.second + ye[i];
if (x >= 0 && y >= 0 && x < 21 - get<0>(large_piece[index]) && y < 21 - get<1>(large_piece[index]) && failed[x][y] == 0) {
go[now_moving][index] = make_pair(x, y);
failed[x][y] = 1;
now_moving++;
}
}
}
}
int unchanged = 0;
for (int tere = 0; tere < 4000; ++tere) {
int pre_grid[20][20] = {};
REP(i, 20) {
REP(q, 20) {
pre_grid[i][q] = max(grid[i][q] - loop_cnt, 0);
}
}
vector<int> next_index;
vector<pair<int, int>> gea;
REP(i, 8) {
next_index.push_back((i));
gea.push_back(make_pair(-1, -1));
}
REP(i, 100) {
int hoge = xor128() % 7;
swap(next_index[hoge], next_index[hoge + 1]);
}
REP(te, 8) {
int index = next_index[te];
if (remaining_turn < get<2>(large_piece[index])) continue;
int donot[20][20] = {};
for (int tea = 0; tea < (21 - get<0>(large_piece[index]))*(21 - get<1>(large_piece[index])); ++tea) {
pair<int, int> now = go[tea][index];
if (donot[now.first][now.second] == 0) {
int ng = 0;
int getting_ok = 0;
for (int i = get<0>(large_piece[index]) - 1; i >= 0; --i) {
for (int q = get<1>(large_piece[index]) - 1; q >= 0; --q) {
int x = i + now.first;
int y = q + now.second;
getting_ok = max(getting_ok, grid[x][y]);
if (pre_grid[x][y] != 0) {
ng = 1;
REP(t, get<0>(large_piece[index])) {
REP(j, get<1>(large_piece[index])) {
int xt = x - t;
int yt = y - j;
if (xt >= 0 && yt >= 0) {
donot[xt][yt] = 1;
}
}
}
break;
}
}
if (ng == 1) break;
}
if (remaining_turn < getting_ok + get<2>(large_piece[index])) {
ng = 1;
}
if (ng == 0) {
REP(i, get<0>(large_piece[index])) {
REP(q, get<1>(large_piece[index])) {
int x = i + now.first;
int y = q + now.second;
pre_grid[x][y] = get<2>(large_piece[index]) + 1;
}
}
gea[index] = now;
break;
}
}
}
}
double ans = 0;
double pre_cnt = 0;
int bobo = 0;
for (int i = 0; i < 8; ++i) {
if (gea[i].first != -1) {
bobo = 1;
if (remaining_turn >= 100) {
ans += get<0>(large_piece[i]) * get<1>(large_piece[i]);
}
else {
ans += (double)get<3>(large_piece[i]) / (double)get<2>(large_piece[i]);
}
if (gea[i].first != 0) {
for (int q = 0; q < get<1>(large_piece[i]); ++q) {
pre_cnt += abs(pre_grid[gea[i].first - 1][gea[i].second + q] - pre_grid[gea[i].first][gea[i].second + q]);
}
}
if (gea[i].first + get<0>(large_piece[i]) < 20) {
for (int q = 0; q < get<1>(large_piece[i]); ++q) {
pre_cnt += abs(pre_grid[gea[i].first + get<0>(large_piece[i])][gea[i].second + q] - pre_grid[gea[i].first + get<0>(large_piece[i]) - 1][gea[i].second + q]);
}
}
if (gea[i].second != 0) {
REP(q, get<0>(large_piece[i])) {
pre_cnt += abs(pre_grid[gea[i].first + q][gea[i].second - 1] - pre_grid[gea[i].first + q][gea[i].second]);
}
}
if (gea[i].second + get<1>(large_piece[i]) < 20) {
REP(q, get<0>(large_piece[i])) {
pre_cnt += abs(pre_grid[gea[i].first + q][gea[i].second + get<1>(large_piece[i])] - pre_grid[gea[i].first + q][gea[i].second + get<1>(large_piece[i]) - 1]);
}
}
}
}
if (bobo == 0 || failed_cnt < 8) {
if (loop_cnt >= 30) break;
failed_cnt++;
loop_cnt++;
if (bobo == 0) failed_cnt = 0;
continue;
}
if (now_ans < ans || (remaining_turn >= 100 && now_ans - 10 < ans&&bea > pre_cnt)) {
now_ans = max(ans, now_ans);
bea = pre_cnt;
winner = gea;
unchanged = 0;
}
else {
unchanged++;
if (unchanged >= 100) break;
}
}
double now_minnest = 0;
int itr = -1;
int next_closest = 100000000;
for (int i = 0; i < 8; ++i) {
if (winner[i].first != -1) {
int maxest = -1;
int minnest = 10000;
REP(q, get<0>(large_piece[i])) {
REP(j, get<1>(large_piece[i])) {
int x = q + winner[i].first;
int y = j + winner[i].second;
maxest = max(maxest, grid[x][y]);
minnest = min(minnest, grid[x][y]);
}
}
REP(q, get<0>(large_piece[i])) {
REP(j, get<1>(large_piece[i])) {
int x = q + winner[i].first;
int y = j + winner[i].second;
bad[x][y] = maxest - 1;
}
}
if (next_closest > maxest || (next_closest == maxest && (double)get<3>(large_piece[itr]) / (double)get<2>(large_piece[itr]) > now_minnest)) {
now_minnest = (double)get<3>(large_piece[itr]) / (double)get<2>(large_piece[itr]);
next_closest = maxest;
itr = i;
}
}
}
if (itr != -1) {
return make_tuple(itr + 8, winner[itr].first, winner[itr].second);
}
return make_tuple(-1, 0, 0);
}
tuple<int, int, int> thinking() {
REP(i, 20) {
REP(q, 20) {
bad[i][q]--;
}
}
if (expected == make_tuple(-1, 0, 0)) {
expected = next();
}
if (expected != make_tuple(-1, 0, 0)) {
int index = get<0>(expected) - 8;
int ng = 0;
REP(i, get<0>(large_piece[index])) {
REP(q, get<1>(large_piece[index])) {
int x = i + get<1>(expected);
int y = q + get<2>(expected);
if (grid[x][y] != 0) {
ng = 1;
break;
}
}
}
if (ng == 0) {
tuple<int, int, int> hoge = expected;
expected = make_tuple(-1, 0, 0);
return hoge;
}
}
//return make_tuple(-1, 0, 0);
//small piece
vector<pair<int, int>> next_index;
REP(i, 8) {
next_index.push_back(make_pair(get<0>(small_piece[i])*get<1>(small_piece[i]), i));
}
sort(next_index.begin(), next_index.end(), greater<pair<int, int>>());
REP(te, 8) {
int index = next_index[te].second;
pair<int, int> go[500];
int deleted[20][20] = {};
int now_moving = 4;
go[0] = (make_pair(0, 0));
go[1] = (make_pair(20 - get<0>(small_piece[index]), 0));
go[2] = (make_pair(0, 20 - get<1>(small_piece[index])));
go[3] = (make_pair(20 - get<0>(small_piece[index]), 20 - get<1>(small_piece[index])));
int xe[4] = { 1,-1,0,0 };
int ye[4] = { 0,0,1,-1 };
for (int tea = 0; tea < (21 - get<0>(small_piece[index]))*(21 - get<1>(small_piece[index])); ++tea) {
int i = go[tea].first;
int q = go[tea].second;
REP(j, 4) {
int x = i + xe[j];
int y = q + ye[j];
if (x >= 0 && x < 21 - get<0>(small_piece[index]) && y >= 0 && y < 21 - get<1>(small_piece[index]) && deleted[x][y] == 0) {
deleted[x][y] = 1;
go[now_moving] = make_pair(x, y);
now_moving++;
}
}
int ok = 1;
int geko = 1000;
REP(j, get<0>(small_piece[index])) {
REP(t, get<1>(small_piece[index])) {
if (i + j < 20 && q + t < 20 && grid[i + j][q + t] == 0 && (bad[i + j][q + t] >= get<2>(small_piece[index]))) {
geko = min(geko, bad[i + j][q + t]);
}
else {
ok = 0;
}
}
}
if (ok == 1 && get<2>(small_piece[index]) <= remaining_turn) {
return make_tuple(index, i, q);
}
}
}
return make_tuple(-1, 0, 0);
}
//------------------------------------------------------------------------------
/// コンストラクタ。
/// @detail 最初のステージ開始前に実行したい処理があればここに書きます。
Answer::Answer()
{
}
//------------------------------------------------------------------------------
/// デストラクタ。
/// @detail 最後のステージ終了後に実行したい処理があればここに書きます。
Answer::~Answer()
{
}
//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出される処理。
/// @detail 各ステージに対する初期化処理が必要ならここに書きます。
/// @param aStage 現在のステージ。
void Answer::init(const Stage& aStage)
{
expected = make_tuple(-1, 0, 0);
remaining_turn = 1000;
for (int i = 0; i < 20; ++i) {
for (int q = 0; q < 20; ++q) {
grid[i][q] = 0;
bad[i][q] = 10000;
}
}
}
//------------------------------------------------------------------------------
/// このターンでの行動を指定する。
/// @detail 希望する行動を Action の static 関数で生成して return してください。
/// 正常ではない行動を return した場合、何も起きません。
/// 詳細は Action のヘッダを参照してください。
/// @param aStage 現在のステージ。
Action Answer::decideNextAction(const Stage& aStage)
{
// 解答コードのサンプルです
//おそらく自分で書いたほうがわかりやすい
//turn経過処理
remaining_turn--;
for (int i = 0; i < 20; ++i) {
for (int q = 0; q < 20; ++q) {
grid[i][q]--;
grid[i][q] = max(0, grid[i][q]);
}
}
//おわり
//クッキー生地の候補取得
for (int i = 0; i < 8; ++i) {
const auto& piece = aStage.candidateLane(CandidateLaneType_Small).pieces()[i];
small_piece[i] = make_tuple(piece.width(), piece.height(), piece.requiredHeatTurnCount(), piece.score());
}
for (int i = 0; i < 8; ++i) {
const auto& piece = aStage.candidateLane(CandidateLaneType_Large).pieces()[i];
large_piece[i] = make_tuple(piece.width(), piece.height(), piece.requiredHeatTurnCount(), piece.score());
}
//おわり
//計算部分は分離
tuple<int, int, int> received = thinking();
if (get<0>(received) == -1) {
return Action::Wait();
}
else if (get<0>(received) < 8) {
REP(i, get<0>(small_piece[get<0>(received)])) {
REP(q, get<1>(small_piece[get<0>(received)])) {
grid[get<1>(received) + i][get<2>(received) + q] = get<2>(small_piece[get<0>(received)]) + 1;
}
}
Vector2i putPos(get<1>(received), get<2>(received));
return Action::Put(CandidateLaneType_Small, get<0>(received), putPos);
}
else {
REP(i, get<0>(large_piece[get<0>(received) - 8])) {
REP(q, get<1>(large_piece[get<0>(received) - 8])) {
grid[get<1>(received) + i][get<2>(received) + q] = get<2>(large_piece[get<0>(received) - 8]) + 1;
}
}
Vector2i putPos(get<1>(received), get<2>(received));
return Action::Put(CandidateLaneType_Large, get<0>(received) - 8, putPos);
}
}
//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出される処理。
/// @detail 各ステージに対する終了処理が必要ならここに書きます。
/// @param aStage 現在のステージ。
void Answer::finalize(const Stage& aStage)
{
}
} // namespace