結果
| 問題 |
No.5019 Hakai Project
|
| ユーザー |
 jupiro
|
| 提出日時 | 2023-11-17 14:52:45 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 64 ms / 3,000 ms |
| コード長 | 9,048 bytes |
| コンパイル時間 | 2,851 ms |
| コンパイル使用メモリ | 233,976 KB |
| 実行使用メモリ | 6,548 KB |
| スコア | 2,103,390,626 |
| 最終ジャッジ日時 | 2023-11-17 14:52:57 |
| 合計ジャッジ時間 | 11,375 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <bits/stdc++.h>
constexpr int inf = (int)1e9 + 7;
constexpr int N = 50, M = 20;
constexpr int dr[] = {1, 0, -1, 0};
constexpr int dc[] = {0, 1, 0, -1};
using Board = std::array<std::array<int, N>, N>;
struct Bomb
{
int bomb_id;
int C, L;
std::vector<int> dr, dc;
Bomb() {}
void input()
{
std::cin >> this->C >> this->L;
this->dr.resize(this->L), this->dc.resize(this->L);
for (int i = 0; i < this->L; i++)
{
std::cin >> this->dr[i] >> this->dc[i];
}
}
};
void input(Board &board, std::array<Bomb, M> &Bombs)
{
int _n, _m;
std::cin >> _n >> _m;
for (int i = 0; i < N; i++)
{
std::string s;
std::cin >> s;
for (int j = 0; j < N; j++)
{
if (s[j] == '.')
board[i][j] = 0;
if (s[j] == '@')
board[i][j] = 1;
if (s[j] == '#')
board[i][j] = 2;
}
}
for (int i = 0; i < M; i++)
{
Bombs[i].input();
Bombs[i].bomb_id = i;
}
}
bool is_board_valid(const int r, const int c)
{
return 0 <= r and r < N and 0 <= c and c < N;
}
std::pair<int, int> calc_wall_and_store_count(const int r, const int c, const Board &board, const Bomb &bomb)
{
int wall = 0, store = 0;
for (int i = 0; i < bomb.L; i++)
{
const int nr = r + bomb.dr[i];
const int nc = c + bomb.dc[i];
if (is_board_valid(nr, nc))
{
if (board[nr][nc] == 1)
store += 1;
if (board[nr][nc] == 2)
wall += 1;
}
}
return std::pair<int, int>{store, wall};
}
void calc_dist(const int sr, const int sc, std::array<std::array<int, N>, N> &dist, std::array<std::array<std::pair<int, int>, N>, N> &back, const Board &board)
{
for (int i = 0; i < N; i++)
{
std::fill(dist[i].begin(), dist[i].end(), inf);
std::fill(back[i].begin(), back[i].end(), std::pair{-1, -1});
}
using T = std::tuple<int, int, int>;
std::queue<T> q1, q2;
dist[sr][sc] = 0;
q1.emplace(0, sr, sc);
while (not q1.empty() or not q2.empty())
{
int d = -1, r = -1, c = -1;
if (not q1.empty() and not q2.empty())
{
if (std::get<0>(q1.front()) <= std::get<0>(q2.front()))
{
std::tie(d, r, c) = q1.front();
q1.pop();
}
else
{
std::tie(d, r, c) = q2.front();
q2.pop();
}
}
else if (not q1.empty())
{
std::tie(d, r, c) = q1.front();
q1.pop();
}
else if (not q2.empty())
{
std::tie(d, r, c) = q2.front();
q2.pop();
}
else
{
assert(false);
}
if (d > dist[r][c])
continue;
for (int i = 0; i < 4; i++)
{
const int nr = r + dr[i];
const int nc = c + dc[i];
if (is_board_valid(nr, nc))
{
if (board[nr][nc] == 0 and dist[nr][nc] > dist[r][c] + 1)
{
dist[nr][nc] = dist[r][c] + 1;
back[nr][nc] = {r, c};
q1.emplace(dist[nr][nc], nr, nc);
}
if (board[nr][nc] != 0 and dist[nr][nc] > dist[r][c] + 2)
{
dist[nr][nc] = dist[r][c] + 2;
back[nr][nc] = {r, c};
q2.emplace(dist[nr][nc], nr, nc);
}
}
}
}
}
void calc_path(const int sr, const int sc, const int er, const int ec, std::vector<std::pair<int, int>> &res, const std::array<std::array<std::pair<int, int>, N>, N> &back)
{
std::vector<int> path;
int cr = er, cc = ec;
while (cr != sr or cc != sc)
{
for (int i = 0; i < 4; i++)
{
const int pr = cr - dr[i];
const int pc = cc - dc[i];
if (is_board_valid(pr, pc) and back[cr][cc] == std::pair<int, int>{pr, pc})
{
path.emplace_back(i);
cr = pr, cc = pc;
}
}
}
while (not path.empty())
{
res.emplace_back(1, path.back());
path.pop_back();
}
}
void solve(Board board, const std::array<Bomb, M> &bombs)
{
std::array<std::array<int, N>, N> dist;
std::array<std::array<std::pair<int, int>, N>, N> back;
std::set<std::pair<int, int>> store_set, wall_set;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (board[i][j] == 1)
store_set.emplace(i, j);
if (board[i][j] == 2)
wall_set.emplace(i, j);
}
}
int min_bomb_id = -1;
{
int max_l = -1;
int min_c = inf;
for (int i = 0; i < M; i++)
{
if (bombs[i].C < min_c or (bombs[i].C == min_c and max_l < bombs[i].L))
{
min_c = bombs[i].C;
min_bomb_id = i;
max_l = bombs[i].L;
}
}
}
std::vector<std::pair<int, int>> res;
std::vector<std::pair<int, int>> gomi;
int sr = 0, sc = 0;
while (not store_set.empty())
{
calc_dist(sr, sc, dist, back, board);
long long res_score = -(long long)inf * 1000;
int r = -1, c = -1;
int res_store_r = -1, res_store_c = -1;
int bomb_id = -1;
int d = inf;
for (const auto &[to_r, to_c] : store_set)
{
if (dist[to_r][to_c] < d)
{
res_store_r = to_r;
res_store_c = to_c;
d = dist[to_r][to_c];
}
}
calc_path(sr, sc, res_store_r, res_store_c, res, back);
calc_dist(res_store_r, res_store_c, dist, back, board);
auto f = [&](const int tr, const int tc) -> void
{
if (not is_board_valid(tr, tc))
return;
{
auto i = min_bomb_id;
auto [erase_store, erase_wall] = calc_wall_and_store_count(tr, tc, board, bombs[i]);
const long long score = erase_wall + erase_store;
if (erase_wall + erase_store > 0 and res_score < score and not(erase_wall < (int)wall_set.size() and erase_store == (int)store_set.size()))
{
res_score = score;
bomb_id = i;
r = tr, c = tc;
}
}
};
gomi.clear();
for (int tr = res_store_r - 10; tr <= res_store_r + 10; tr++)
{
for (int tc = res_store_c - 10; tc <= res_store_c + 10; tc++)
{
if (is_board_valid(tr, tc))
gomi.emplace_back(tr, tc);
}
}
std::sort(gomi.begin(), gomi.end(), [&](auto i, auto j)
{ return dist[i.first][i.second] > dist[j.first][j.second]; });
while (not gomi.empty())
{
f(gomi.back().first, gomi.back().second);
gomi.pop_back();
if (res_score == bombs[min_bomb_id].L)
gomi.clear();
}
if (bomb_id == -1)
{
for (int tr = 0; tr < N; tr++)
{
for (int tc = 0; tc < N; tc++)
{
if (not is_board_valid(tr, tc))
continue;
f(tr, tc);
}
}
}
if (bomb_id == -1)
break;
assert(board[res_store_r][res_store_c] == 1);
res.emplace_back(2, bomb_id + 1);
calc_path(res_store_r, res_store_c, r, c, res, back);
res.emplace_back(3, bomb_id + 1);
sr = r, sc = c;
assert(0 <= bomb_id and bomb_id < M);
const auto &bomb = bombs[bomb_id];
for (int i = 0; i < bomb.L; i++)
{
const int nr = r + bomb.dr[i];
const int nc = c + bomb.dc[i];
if (is_board_valid(nr, nc))
{
if (board[nr][nc] == 1)
{
store_set.erase(store_set.find({nr, nc}));
}
if (board[nr][nc] == 2)
{
wall_set.erase(wall_set.find({nr, nc}));
}
board[nr][nc] = 0;
}
}
}
const std::string DIR = "DRUL";
std::cout << res.size() << "\n";
int cost2 = 0;
for (const auto &[t, val] : res)
{
if (t == 1)
{
std::cout << 1 << " " << DIR[val] << "\n";
}
else
{
std::cout << t << " " << val << "\n";
if (t == 2)
{
cost2 += bombs[val - 1].C;
}
}
}
std::cerr << cost2 << "\n";
}
int main()
{
Board board;
std::array<Bomb, M> bombs;
input(board, bombs);
solve(board, bombs);
}