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 |
|
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 |