Submission #2554884


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[15 * 8][1 << 20];
int32_t func(int i, std::bitset<20> mask, std::pair<int,int> posi)
{
	if (posi.first >= H) {
		return 0;
	}
	int32_t a=-1;
	auto& memo = a;// 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 << (int)v << endl;
	}


	return 0;
}
#endif

Submission Info

Submission Time
Task F - Phutball
User eiya
Language C++14 (Clang 3.8.0)
Score 0
Code Size 3554 Byte
Status WA
Exec Time 328 ms
Memory 632 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 78
WA × 15
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 AC 5 ms 632 KB
00-sample2.txt AC 1 ms 256 KB
00-sample3.txt AC 1 ms 256 KB
00-sample4.txt AC 1 ms 256 KB
00-sample5.txt AC 1 ms 256 KB
00-sample6.txt AC 1 ms 256 KB
random-000.txt AC 1 ms 256 KB
random-001.txt AC 1 ms 256 KB
random-002.txt AC 1 ms 256 KB
random-003.txt WA 1 ms 256 KB
random-004.txt AC 1 ms 256 KB
random-005.txt AC 1 ms 256 KB
random-006.txt AC 1 ms 256 KB
random-007.txt AC 1 ms 256 KB
random-008.txt AC 1 ms 256 KB
random-009.txt AC 1 ms 256 KB
random-010.txt AC 1 ms 256 KB
random-011.txt WA 1 ms 256 KB
random-012.txt AC 1 ms 256 KB
random-013.txt AC 1 ms 256 KB
random-014.txt AC 1 ms 256 KB
random-015.txt AC 1 ms 256 KB
random-016.txt AC 1 ms 256 KB
random-017.txt AC 1 ms 256 KB
random-018.txt AC 1 ms 256 KB
random-019.txt AC 1 ms 256 KB
random-020.txt WA 1 ms 256 KB
random-021.txt AC 1 ms 256 KB
random-022.txt WA 1 ms 256 KB
random-023.txt WA 1 ms 256 KB
random-024.txt AC 1 ms 256 KB
random-025.txt AC 1 ms 256 KB
random-026.txt AC 1 ms 256 KB
random-027.txt AC 1 ms 256 KB
random-028.txt WA 1 ms 256 KB
random-029.txt AC 1 ms 256 KB
random-030.txt AC 1 ms 256 KB
random-031.txt AC 1 ms 256 KB
random-032.txt AC 1 ms 256 KB
random-033.txt AC 1 ms 256 KB
random-034.txt AC 1 ms 256 KB
random-035.txt AC 1 ms 256 KB
random-036.txt WA 1 ms 256 KB
random-037.txt AC 1 ms 256 KB
random-038.txt AC 1 ms 256 KB
random-039.txt AC 1 ms 256 KB
random-040.txt AC 1 ms 256 KB
random-041.txt WA 1 ms 256 KB
random-042.txt WA 1 ms 256 KB
random-043.txt AC 1 ms 256 KB
random-044.txt AC 1 ms 256 KB
random-045.txt WA 1 ms 256 KB
random-046.txt AC 1 ms 256 KB
random-047.txt AC 1 ms 256 KB
random-048.txt AC 1 ms 256 KB
random-049.txt AC 1 ms 256 KB
random-050.txt AC 1 ms 256 KB
random-051.txt AC 1 ms 256 KB
random-052.txt AC 1 ms 256 KB
random-053.txt AC 1 ms 256 KB
random-054.txt AC 1 ms 256 KB
random-055.txt AC 1 ms 256 KB
random-056.txt AC 1 ms 256 KB
random-057.txt AC 1 ms 256 KB
random-058.txt AC 1 ms 256 KB
random-059.txt AC 1 ms 256 KB
random-060.txt AC 1 ms 256 KB
random-061.txt AC 1 ms 256 KB
random-062.txt AC 1 ms 256 KB
random-063.txt AC 1 ms 256 KB
random-064.txt AC 1 ms 256 KB
random-065.txt AC 1 ms 256 KB
random-066.txt AC 1 ms 256 KB
random-067.txt WA 1 ms 256 KB
random-068.txt AC 1 ms 256 KB
random-069.txt AC 1 ms 256 KB
random-070.txt AC 1 ms 256 KB
random-071.txt AC 1 ms 256 KB
random-072.txt AC 1 ms 256 KB
random-073.txt AC 1 ms 256 KB
random-074.txt WA 1 ms 256 KB
random-075.txt AC 1 ms 256 KB
random-076.txt WA 1 ms 256 KB
random-077.txt AC 1 ms 256 KB
random-078.txt AC 1 ms 256 KB
random-079.txt AC 1 ms 256 KB
test01.txt WA 1 ms 256 KB
test02.txt AC 7 ms 256 KB
test03.txt AC 17 ms 256 KB
test04.txt AC 327 ms 256 KB
test05.txt AC 328 ms 256 KB
test06.txt WA 82 ms 256 KB
test07.txt AC 1 ms 256 KB