結果
問題 | No.5019 Hakai Project |
ユーザー |
|
提出日時 | 2023-11-19 21:06:22 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,229 bytes |
コンパイル時間 | 2,876 ms |
コンパイル使用メモリ | 166,856 KB |
実行使用メモリ | 6,676 KB |
スコア | 6 |
最終ジャッジ日時 | 2023-11-19 21:06:32 |
合計ジャッジ時間 | 8,938 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 WA * 44 |
ソースコード
#define NOMINMAX#define TEST_MODE true#define _CRT_SECURE_NO_WARNINGS#define _USE_MATH_DEFINES#include "bits/stdc++.h"#include <regex>using namespace std;#define rep(i,n) for(int i=0;i<(int)(n);++i)#define rep2(i,a,b) for(int i=(a);i<(int)(b);++i)#define rrep(i,n) for(int i=(n)-1;i>=0;--i)#define rrep2(i,a,b) for(int i=(a)-1;i>=(int)b;--i)#define range(i,a,b,c) for(int i=a;c>0?i<b:i>b;i+=c)#define chmax(a,b) (a=(a)<(b)?(b):(a))#define chmin(a,b) (a=(a)>(b)?(b):(a))//template<typename T>void out(T a) {T b=a;if(a==inf)b=-1;cout<<a<<endl;}//#define out(a) cout<<(a)<<endl//#define o2(a,b) cout<<(a)<<" ";out(b)//#define o3(a,b,c) cout<<(a)<<" ";o2(b, c)#define abp(o,a,b) out(((o)?a:b))#define YEP(x) abp(x,"YES","NO")#define Yep(x) abp(x,"Yes","No")using ll = long long;using ull = unsigned long long;using ld = long double;#define all(a) begin(a),end(a)#define ifnot(a) if(!(a))#define int long long#ifdef LOCAL_ENV#if TEST_MODE==trueconst bool test = true;#define dump(x) cerr<<#x<<" : "<<(x)<< " "#define dumpl(x) dump(x)<<endl#define cerr_endl cerr<<endl#elseconst bool test = false;#define dump(x)#define dumpl(x)#define cerr_endl#endif#elseconst bool test = false;#define dump(x)#define dumpl(x)#endifint dx[] = { 1,0,-1,0 };int dy[] = { 0,1,0,-1 };const int inf = (int)1 << 60;const int undefined = inf;const ll INFL = (ll)1 << 60;ll mod_n = (int)1e9 + 7;const double eps = 1e-10;typedef long double Real;// return -1, 0, 1int sgn(const Real& r) { return(r > eps) - (r < -eps); }int sgn(const Real& a, const Real& b) { return sgn(a - b); }const int MAX = (int)2e6 + 5;const int MAX2 = 2005;vector<string> split(const string& str, char sep) { vector<string> v; stringstream ss(str); string buffer; while (getline(ss, buffer, sep)) v.push_back(buffer); return v; }string join(const vector<string>& v, const string delim = 0) { string s; if (!v.empty()) { s += v[0]; for (decltype(v.size()) i = 1, c = v.size(); i< c; ++i) { if (delim != "")s += delim; s += v[i]; } }return s; }string operator*(const string& s, const int& n) { string res = ""; rep(i, n)res += s; return res; }#define sum_f(a){return accumulate(all(a),0ll);}template<typename T>T gcd(T a, T b) { T c; while (a != 0) { c = a; a = b % a; b = c; }; return b; }template<typename T>T bit_count(T N) { T c = 0; while (N) { if (N & 1)c++; N >>= 1; }return c; }template<typename T>void print_vec(vector<T> a, ostream& o = cout) { rep(i, a.size() - 1)o << a[i] << " "; o << a.back() << endl; }ll pow_n(ll x, ll n) { ll r = 1; while (n > 0) { if (n & 1)r = r * x; x = x * x; n >>= 1; }return r; }int H, W;#define grid_ng(y,x) (y<0||y>=H||x<0||x>=W)int div_ceil(int a, int b) { int r = a / b; if (a % b != 0)r++; return r; }#define i1(a) cin>>a;#define i2(a,b) cin>>a>>b;#define i3(a,b,c) cin>>a;i2(b,c);#define i4(a,b,c,d) cin>>a;i3(b,c,d);#define i5(a,b,c,d,e) cin>>a;i4(b,c,d,e);int cx = 0, cy = 0;void changeXY(char c) {if (c == 'U') cy = cy + 1;else if (c == 'D') cy = cy - 1;else if (c == 'R') cx = cx + 1;else cx = cx - 1;}template<typename T>void in_vec(vector<T>& a, int n) {a.resize(n);rep(i, n) cin >> a[i];}template<typename T>void in_vec(vector<vector<T>>& a) {a.resize(H);rep(i, H) {a[i].resize(W);rep(j, W) cin >> a[i][j];}}template<typename First>void out(First first) {cout << first << endl;}template<typename First, typename... Rest>void out(First first, Rest... rest) {cout << first << " ";out(rest...);}template<class T, size_t n, size_t idx = 0>auto make_vec(const size_t(&d)[n], const T& init) noexcept {if constexpr (idx < n) return std::vector(d[idx], make_vec<T, n, idx + 1>(d, init));else return init;}template<class T, size_t n>auto make_vec(const size_t(&d)[n]) noexcept {return make_vec(d, T{});}bool is_bit_on(int b, int i) {return (b >> i) & 1;}// end templatestruct Bomb {int cost, original_id;vector<pair<int, int>> places;bool operator<(const Bomb& rhs) const {return places.size() < rhs.places.size();}};vector<string> field;vector<pair<int, string>> ans;vector<int> bomb_cnt;vector<Bomb> bomb;int bomb_id = 0;int n, m;int buy_cnt = 10;int Player_x = 0, Player_y = 0;int total_building = 0;int total_store = 0;void print_ans(pair<int, string> p) {// cout << p.first << " " << p.second << endl;ans.push_back(p);}void player_move(int move_x, int move_y) {if (move_x > 0) {rep(j, move_x) {print_ans(make_pair(1, "R"));}}else {rep(j, -move_x) {print_ans(make_pair(1, "L"));}}if (move_y > 0) {rep(j, move_y) {print_ans(make_pair(1, "D"));}}else {rep(j, -move_y) {print_ans(make_pair(1, "U"));}}Player_x += move_x;Player_y += move_y;}int calc_store_cnt_if_used(int y, int x, int use_bomb_id) {int store = 0;auto a = bomb[use_bomb_id].places;rep(i, a.size()) {int ny = y + bomb[use_bomb_id].places[i].first;int nx = x + bomb[use_bomb_id].places[i].second;if (grid_ng(ny, nx)) continue;if (field[ny][nx] == '@') {store++;}}return store;}bool act_near_place(int y, int x, function< bool(int, int) > f) {rep(dist, H + W) {rep2(dx, -dist, dist + 1) {rep(i, 2) {int dy = dist - abs(dx);if (i == 1) dy = -dy;int nx = x + dx;int ny = y + dy;if (grid_ng(ny, nx)) continue;//dumpl(dy);//dumpl(dx);if (f(ny, nx)) return false;}}}return true;}void walk_to_near_building(int y, int x) {act_near_place(y, x, [&](int ny, int nx) {int score_cnt = calc_store_cnt_if_used(ny, nx, bomb_id);// dumpl(score_cnt);if ((total_store <= score_cnt) && (total_building != total_store)) return false;if (field[ny][nx] != '.') {int move_x = nx - x;int move_y = ny - y;player_move(move_x, move_y);return true;}return false;});}bool buy_near_bomb(int y, int x) {return act_near_place(y, x, [&](int ny, int nx) {if (field[ny][nx] == '@') {int move_x = nx - x;int move_y = ny - y;player_move(move_x, move_y);bomb_cnt[bomb_id] += buy_cnt;rep(k, buy_cnt) {print_ans(make_pair(2, to_string(bomb_id + 1)));}player_move(-move_x, -move_y);return true;}return false;});}void use_bomb(int y, int x, int use_bomb_id) {if (bomb_cnt[use_bomb_id] <= 0) return;bomb_cnt[use_bomb_id]--;print_ans(make_pair(3, to_string(bomb[use_bomb_id].original_id + 1)));auto a = bomb[use_bomb_id].places;rep(i, a.size()) {int ny = y + bomb[use_bomb_id].places[i].first;int nx = x + bomb[use_bomb_id].places[i].second;if (grid_ng(ny, nx)) continue;if (field[ny][nx] != '.') {if (field[ny][nx] == '@') total_store--;total_building--;field[ny][nx] = '.';}}}void print_field() {rep(i, H) {rep(j, W) {cerr << field[i][j];}cerr << endl;}}void solve() {rep(i, H) {rep(j, W) {if (field[i][j] != '.') total_building++;if (field[i][j] == '@') total_store++;}}walk_to_near_building(Player_y, Player_x);while (total_building > 0) {dumpl(total_building);if (bomb_cnt[bomb_id] < buy_cnt) {bool cannot = buy_near_bomb(Player_y, Player_x);if (cannot) {return;}}if (field[Player_y][Player_x] != '.') {use_bomb(Player_y, Player_x, bomb_id);walk_to_near_building(Player_y, Player_x);}else {dumpl("cannot use bomb");return;}}}signed main() {cin >> n >> m;H = n;W = n;field.resize(H);for (int i = 0; i < H; i++) {cin >> field[i];}bomb.resize(m);bomb_cnt.resize(m);for (int i = 0; i < m; i++) {int C, L;cin >> C >> L;bomb[i].cost = C;bomb[i].original_id = i;for (int j = 0; j < L; j++) {int a, b;cin >> a >> b;bomb[i].places.push_back(make_pair(a, b));}}sort(all(bomb));solve();cout << ans.size() << endl;for (pair<int, string> i : ans) {cout << i.first << " " << i.second << endl;}print_field();}