結果
問題 | No.5019 Hakai Project |
ユーザー | merom686 |
提出日時 | 2023-11-17 16:21:55 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 5 ms / 3,000 ms |
コード長 | 4,196 bytes |
コンパイル時間 | 3,286 ms |
コンパイル使用メモリ | 267,632 KB |
実行使用メモリ | 6,676 KB |
スコア | 1,050,437,967 |
最終ジャッジ日時 | 2023-11-17 16:22:04 |
合計ジャッジ時間 | 8,832 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
6,676 KB |
testcase_01 | AC | 4 ms
6,676 KB |
testcase_02 | AC | 4 ms
6,676 KB |
testcase_03 | AC | 4 ms
6,676 KB |
testcase_04 | AC | 5 ms
6,676 KB |
testcase_05 | AC | 5 ms
6,676 KB |
testcase_06 | AC | 4 ms
6,676 KB |
testcase_07 | AC | 4 ms
6,676 KB |
testcase_08 | AC | 4 ms
6,676 KB |
testcase_09 | AC | 4 ms
6,676 KB |
testcase_10 | AC | 4 ms
6,676 KB |
testcase_11 | AC | 5 ms
6,676 KB |
testcase_12 | AC | 4 ms
6,676 KB |
testcase_13 | AC | 4 ms
6,676 KB |
testcase_14 | AC | 4 ms
6,676 KB |
testcase_15 | AC | 5 ms
6,676 KB |
testcase_16 | AC | 4 ms
6,676 KB |
testcase_17 | AC | 4 ms
6,676 KB |
testcase_18 | AC | 4 ms
6,676 KB |
testcase_19 | AC | 4 ms
6,676 KB |
testcase_20 | AC | 4 ms
6,676 KB |
testcase_21 | AC | 4 ms
6,676 KB |
testcase_22 | AC | 5 ms
6,676 KB |
testcase_23 | AC | 4 ms
6,676 KB |
testcase_24 | AC | 4 ms
6,676 KB |
testcase_25 | AC | 4 ms
6,676 KB |
testcase_26 | AC | 4 ms
6,676 KB |
testcase_27 | AC | 5 ms
6,676 KB |
testcase_28 | AC | 5 ms
6,676 KB |
testcase_29 | AC | 5 ms
6,676 KB |
testcase_30 | AC | 4 ms
6,676 KB |
testcase_31 | AC | 4 ms
6,676 KB |
testcase_32 | AC | 4 ms
6,676 KB |
testcase_33 | AC | 4 ms
6,676 KB |
testcase_34 | AC | 4 ms
6,676 KB |
testcase_35 | AC | 4 ms
6,676 KB |
testcase_36 | AC | 4 ms
6,676 KB |
testcase_37 | AC | 4 ms
6,676 KB |
testcase_38 | AC | 4 ms
6,676 KB |
testcase_39 | AC | 4 ms
6,676 KB |
testcase_40 | AC | 4 ms
6,676 KB |
testcase_41 | AC | 4 ms
6,676 KB |
testcase_42 | AC | 5 ms
6,676 KB |
testcase_43 | AC | 4 ms
6,676 KB |
testcase_44 | AC | 4 ms
6,676 KB |
testcase_45 | AC | 4 ms
6,676 KB |
testcase_46 | AC | 4 ms
6,676 KB |
testcase_47 | AC | 5 ms
6,676 KB |
testcase_48 | AC | 4 ms
6,676 KB |
testcase_49 | AC | 4 ms
6,676 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int N = 50, M = 20, O = 20, W = 128; char a[N][N + 1]; int c[M], l[M]; array<int, 2000> v[M]; int b[(N + O * 2) * W]; int main() { { int n_, m_; cin >> n_ >> m_; } for (int i = 0; i < N; i++) { cin >> a[i]; } auto f = [&](int i, int j) { return (i + O) * W + j; }; for (int j = 0; j < M; j++) { cin >> c[j] >> l[j]; for (int h = 0; h < l[j]; h++) { int a, b; cin >> a >> b; v[j][h] = f(a - O, b); } } vector<int> u; int w[2] = {}, z = 0; auto bomb = [&](int k, int j) { int n = 0; for (int h = 0; h < l[j]; h++) { int k1 = k + v[j][h]; if (b[k1] == '@' || b[k1] == '#') { n++; } } if (n == 0) return; for (int h = 0; h < l[j]; h++) { int k1 = k + v[j][h]; if (b[k1] == '@' || b[k1] == '#') { w[b[k1] == '#']--; b[k1] = '.'; } } u.push_back(10000 + j); }; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { b[f(i, j)] = a[i][j]; if (a[i][j] == '@' || a[i][j] == '#') w[a[i][j] == '#']++; } } int k0 = f(0, 0); while (1) { //cout << w[0] << ' ' << w[1] << endl; if (w[0] == 0 && w[1] == 0) break; char g = "@#"[w[0] == 0]; vector<int> r((N + O * 2) * W); vector<int> d((N + O * 2) * W, 1 << 30); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { d[f(i, j)] = 1 << 29; } } queue<int> q[3]; int k2 = -1; q[0].push(k0); d[k0] = 0; for (int d0 = 0;; d0++) { while (!q[0].empty()) { int k = q[0].front(); q[0].pop(); if (d[k] != d0) continue; if (b[k] == g) { k2 = k; goto break2; } for (int s : { -1, 1, -W, W }) { int k1 = k + s; if (d[k1] == 1 << 30) continue; int e = 1 + (b[k] != '.'); int d1 = d[k] + e; if (d1 < d[k1]) { d[k1] = d1; q[e].push(k1); r[k1] = s; if (b[k1] == g && e == 1) { k2 = k1; goto break2; } } } } q[0].swap(q[1]); q[1].swap(q[2]); } break2: vector<int> t; while (k2 != k0) { t.push_back(r[k2]); k2 -= r[k2]; } ranges::reverse(t); auto nu = [&]() { if (g == '#') { bomb(k0, 0); return; } if (b[k0] == '@') { u.push_back(0); z = 1; for (int j = 0; j < M; j++) { bomb(k0, j); } } }; nu(); for (const auto &s : t) { if (g == '#') { bomb(k0, 0); } k0 += s; u.push_back(s); } nu(); } ranges::reverse(u); int p[M] = {}; vector<pair<int, int>> r; for (const auto &s : u) { if (s == 0) { for (int j = 0; j < M; j++) { while (p[j] > 0) r.push_back({ 2, j }), p[j]--; } } else if (s >= 10000) { r.push_back({ 3, s - 10000 }); p[s - 10000]++; } else if (!r.empty()) { r.push_back({ 1, "LRUD"[(s == 1) + (s == -W) * 2 + (s == W) * 3] }); } } ranges::reverse(r); cout << r.size() << '\n'; for (const auto &[t, c] : r) { cout << t << ' '; if (t == 1) { cout << (char)c; } else { cout << c + 1; } cout << '\n'; } return 0; }