Submission #2554819


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];
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 (Clang 3.8.0)
Score 0
Code Size 3523 Byte
Status RE
Exec Time 128 ms
Memory 123768 KB

Compile Error

./Main.cpp:65:10: warning: implicit conversion from 'const int32_t' (aka 'const int') to 'int8_t' (aka 'signed char') changes value from 100000 to -96 [-Wconstant-conversion]
                return INF;
                ~~~~~~ ^~~
./Main.cpp:159:8: warning: comparison of constant 100000 with expression of type 'signed char' is always false [-Wtautological-constant-out-of-range-compare]
        if (v == INF) {
            ~ ^  ~~~
2 warnings generated.

Judge Result

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