Submission #2554814


Source Code Expand


#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;


template<typename T, typename U>
std::enable_if_t<std::rank<T>::value == 0> fill_all(T& arr, const U& v) {
	arr = v;
}
template<typename ARR, typename U>
std::enable_if_t<std::rank<ARR>::value != 0> fill_all(ARR& arr, const U& v) {
	for (auto& i : arr) {
		fill_all(i, v);
	}
}

int32_t H=19,W=15;
char map[30][30];
int mapint[30][30];
int32_t start_h, start_w = 0;
std::vector<std::pair<int, int>> pos;
std::map<std::pair<int, int>, int> pos_map;
int postable[21*8];

const int diffh[8] = {0,0,1,1,1,-1,-1,-1};
const int diffw[8] = {-1,1,-1,0,1,-1,0,1};

const int32_t INF = 100000;
int8_t dp[21 * 8][1 << 20];
int8_t func(int i, std::bitset<20> mask, std::pair<int,int> posi)
{
	if (posi.first >= H) {
		return 0;
	}
	auto& memo = dp[postable[i]][mask.to_ulong()];

	if (memo != -1) { return memo; }
	if (posi.second < 0 || posi.second >= W) {
		return INF;
	}

	int32_t res = INF;
	for (size_t cc = 0; cc < 8; cc++)
	{
		int last_index = 0;
		std::bitset<20> nextmask = mask;
		bool ok = false;
		auto t = posi;
		t.first += diffh[cc];
		t.second += diffw[cc];
		if (t.first < 0 || t.first >= H) { continue; }
		if (t.second < 0 || t.second >= W) { continue; }
		while (map[t.first][t.second] == 'X' && mask[mapint[t.first][t.second]] == true)
		{
			ok = true;
			last_index = mapint[t.first][t.second];
			nextmask[mapint[t.first][t.second]] = false;


			t.first += diffh[cc];
			t.second += diffw[cc];
			if (t.first < 0) { ok = false; break; }
			if (t.first >= H) { break; }
			if (t.second < 0 || t.second >= W) { ok = false; break; }
		}

		if (ok) {
			res = std::min(res, func(last_index * 8 + cc, nextmask, t)+1);
		}
	}
	return memo = res;
}

int main()
{
	fill_all(dp, -1);
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	for (size_t i = 0; i < H; i++)
	{
		in >> map[i];
	}

	for (size_t i = 0; i < H; i++)
	{
		for (size_t j = 0; j < W; j++)
		{
			if (map[i][j]=='O')
			{
				start_h = i;
				start_w = j;
			}
			if (map[i][j] == 'X')
			{
				pos.emplace_back(i, j);
				mapint[i][j] = pos.size() - 1;
				auto v = pos.back();
				for (size_t cc = 0; cc < 8; cc++)
				{
					auto t = v;
					t.first += diffh[i];
					t.second += diffw[i];
					pos_map[t] = 0;
				}
			}
		}
	}

	{
		int count = 0;
		for (auto& i : pos_map)
		{
			i.second = count++;
		}
	}

	for (int i = 0;i<pos.size();++i)
	{
		for (size_t cc = 0; cc < 8; cc++)
		{
			auto t = pos[i];
			t.first += diffh[cc];
			t.second += diffw[cc];
			postable[i * 8 + cc] = pos_map[t];
		}
	}
	postable[(pos.size()) * 8] = (pos.size()) * 8;
	auto v = func((pos.size()) * 8, std::bitset<20>((1 << 20) - 1), { start_h, start_w });
	if (v == INF) {
		out << -1 << endl;
	}
	else {
		out << v << endl;
	}


	return 0;
}
#endif

Submission Info

Submission Time
Task F - Phutball
User eiya
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3523 Byte
Status MLE
Exec Time 105 ms
Memory 172416 KB

Compile Error

./Main.cpp: In function ‘int8_t func(int, std::bitset<20ul>, std::pair<int, int>)’:
./Main.cpp:65:10: warning: overflow in implicit constant conversion [-Woverflow]
   return INF;
          ^

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
MLE × 93
Set Name Test Cases
All 00-sample1.txt, 00-sample2.txt, 00-sample3.txt, 00-sample4.txt, 00-sample5.txt, 00-sample6.txt, random-000.txt, random-001.txt, random-002.txt, random-003.txt, random-004.txt, random-005.txt, random-006.txt, random-007.txt, random-008.txt, random-009.txt, random-010.txt, random-011.txt, random-012.txt, random-013.txt, random-014.txt, random-015.txt, random-016.txt, random-017.txt, random-018.txt, random-019.txt, random-020.txt, random-021.txt, random-022.txt, random-023.txt, random-024.txt, random-025.txt, random-026.txt, random-027.txt, random-028.txt, random-029.txt, random-030.txt, random-031.txt, random-032.txt, random-033.txt, random-034.txt, random-035.txt, random-036.txt, random-037.txt, random-038.txt, random-039.txt, random-040.txt, random-041.txt, random-042.txt, random-043.txt, random-044.txt, random-045.txt, random-046.txt, random-047.txt, random-048.txt, random-049.txt, random-050.txt, random-051.txt, random-052.txt, random-053.txt, random-054.txt, random-055.txt, random-056.txt, random-057.txt, random-058.txt, random-059.txt, random-060.txt, random-061.txt, random-062.txt, random-063.txt, random-064.txt, random-065.txt, random-066.txt, random-067.txt, random-068.txt, random-069.txt, random-070.txt, random-071.txt, random-072.txt, random-073.txt, random-074.txt, random-075.txt, random-076.txt, random-077.txt, random-078.txt, random-079.txt, test01.txt, test02.txt, test03.txt, test04.txt, test05.txt, test06.txt, test07.txt
Case Name Status Exec Time Memory
00-sample1.txt MLE 98 ms 172288 KB
00-sample2.txt MLE 98 ms 172288 KB
00-sample3.txt MLE 98 ms 172288 KB
00-sample4.txt MLE 98 ms 172288 KB
00-sample5.txt MLE 98 ms 172288 KB
00-sample6.txt MLE 98 ms 172288 KB
random-000.txt MLE 99 ms 172288 KB
random-001.txt MLE 98 ms 172288 KB
random-002.txt MLE 98 ms 172288 KB
random-003.txt MLE 98 ms 172288 KB
random-004.txt MLE 99 ms 172288 KB
random-005.txt MLE 98 ms 172288 KB
random-006.txt MLE 98 ms 172288 KB
random-007.txt MLE 98 ms 172288 KB
random-008.txt MLE 98 ms 172288 KB
random-009.txt MLE 105 ms 172288 KB
random-010.txt MLE 99 ms 172288 KB
random-011.txt MLE 98 ms 172288 KB
random-012.txt MLE 98 ms 172288 KB
random-013.txt MLE 98 ms 172288 KB
random-014.txt MLE 98 ms 172288 KB
random-015.txt MLE 98 ms 172288 KB
random-016.txt MLE 98 ms 172288 KB
random-017.txt MLE 98 ms 172288 KB
random-018.txt MLE 99 ms 172288 KB
random-019.txt MLE 98 ms 172288 KB
random-020.txt MLE 98 ms 172288 KB
random-021.txt MLE 98 ms 172288 KB
random-022.txt MLE 98 ms 172288 KB
random-023.txt MLE 98 ms 172288 KB
random-024.txt MLE 98 ms 172288 KB
random-025.txt MLE 98 ms 172288 KB
random-026.txt MLE 98 ms 172288 KB
random-027.txt MLE 99 ms 172288 KB
random-028.txt MLE 98 ms 172288 KB
random-029.txt MLE 99 ms 172288 KB
random-030.txt MLE 98 ms 172288 KB
random-031.txt MLE 98 ms 172288 KB
random-032.txt MLE 98 ms 172288 KB
random-033.txt MLE 99 ms 172288 KB
random-034.txt MLE 98 ms 172288 KB
random-035.txt MLE 99 ms 172288 KB
random-036.txt MLE 98 ms 172288 KB
random-037.txt MLE 98 ms 172288 KB
random-038.txt MLE 98 ms 172288 KB
random-039.txt MLE 98 ms 172288 KB
random-040.txt MLE 98 ms 172288 KB
random-041.txt MLE 98 ms 172288 KB
random-042.txt MLE 98 ms 172288 KB
random-043.txt MLE 98 ms 172288 KB
random-044.txt MLE 98 ms 172288 KB
random-045.txt MLE 100 ms 172288 KB
random-046.txt MLE 98 ms 172288 KB
random-047.txt MLE 98 ms 172288 KB
random-048.txt MLE 98 ms 172288 KB
random-049.txt MLE 98 ms 172288 KB
random-050.txt MLE 98 ms 172288 KB
random-051.txt MLE 98 ms 172288 KB
random-052.txt MLE 98 ms 172288 KB
random-053.txt MLE 98 ms 172288 KB
random-054.txt MLE 99 ms 172288 KB
random-055.txt MLE 98 ms 172288 KB
random-056.txt MLE 98 ms 172288 KB
random-057.txt MLE 98 ms 172288 KB
random-058.txt MLE 98 ms 172288 KB
random-059.txt MLE 98 ms 172288 KB
random-060.txt MLE 98 ms 172288 KB
random-061.txt MLE 99 ms 172288 KB
random-062.txt MLE 98 ms 172288 KB
random-063.txt MLE 99 ms 172288 KB
random-064.txt MLE 98 ms 172288 KB
random-065.txt MLE 98 ms 172288 KB
random-066.txt MLE 98 ms 172288 KB
random-067.txt MLE 98 ms 172288 KB
random-068.txt MLE 98 ms 172288 KB
random-069.txt MLE 98 ms 172288 KB
random-070.txt MLE 98 ms 172288 KB
random-071.txt MLE 98 ms 172288 KB
random-072.txt MLE 98 ms 172288 KB
random-073.txt MLE 99 ms 172288 KB
random-074.txt MLE 98 ms 172288 KB
random-075.txt MLE 98 ms 172288 KB
random-076.txt MLE 98 ms 172288 KB
random-077.txt MLE 98 ms 172288 KB
random-078.txt MLE 98 ms 172288 KB
random-079.txt MLE 98 ms 172288 KB
test01.txt MLE 98 ms 172288 KB
test02.txt MLE 100 ms 172416 KB
test03.txt MLE 99 ms 172288 KB
test04.txt MLE 104 ms 172288 KB
test05.txt MLE 104 ms 172288 KB
test06.txt MLE 101 ms 172288 KB
test07.txt MLE 98 ms 172288 KB