#929757 (C++17(clang)) No.5019 Hakai Project

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	naimonon77
提出日時	2023-11-19 21:54:55
言語	C++17(clang) (17.0.6 + boost 1.83.0)
結果	AC
実行時間	19 ms / 3,000 ms
コード長	8,685 bytes
コンパイル時間	3,242 ms
コンパイル使用メモリ	166,740 KB
実行使用メモリ	6,676 KB
スコア	62,313,429
最終ジャッジ日時	2023-11-19 21:55:07
合計ジャッジ時間	10,552 ms
ジャッジサーバーID （参考情報）	judge11 / judge15
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	16 ms 6,676 KB
testcase_01	AC	15 ms 6,676 KB
testcase_02	AC	16 ms 6,676 KB
testcase_03	AC	16 ms 6,676 KB
testcase_04	AC	15 ms 6,676 KB
testcase_05	AC	17 ms 6,676 KB
testcase_06	AC	16 ms 6,676 KB
testcase_07	AC	16 ms 6,676 KB
testcase_08	AC	17 ms 6,676 KB
testcase_09	AC	17 ms 6,676 KB
testcase_10	AC	17 ms 6,676 KB
testcase_11	AC	16 ms 6,676 KB
testcase_12	AC	17 ms 6,676 KB
testcase_13	AC	17 ms 6,676 KB
testcase_14	AC	16 ms 6,676 KB
testcase_15	AC	16 ms 6,676 KB
testcase_16	AC	16 ms 6,676 KB
testcase_17	AC	16 ms 6,676 KB
testcase_18	AC	16 ms 6,676 KB
testcase_19	AC	16 ms 6,676 KB
testcase_20	AC	17 ms 6,676 KB
testcase_21	AC	17 ms 6,676 KB
testcase_22	AC	16 ms 6,676 KB
testcase_23	AC	18 ms 6,676 KB
testcase_24	AC	18 ms 6,676 KB
testcase_25	AC	18 ms 6,676 KB
testcase_26	AC	16 ms 6,676 KB
testcase_27	AC	17 ms 6,676 KB
testcase_28	AC	19 ms 6,676 KB
testcase_29	AC	18 ms 6,676 KB
testcase_30	AC	15 ms 6,676 KB
testcase_31	AC	15 ms 6,676 KB
testcase_32	AC	17 ms 6,676 KB
testcase_33	AC	17 ms 6,676 KB
testcase_34	AC	17 ms 6,676 KB
testcase_35	AC	17 ms 6,676 KB
testcase_36	AC	15 ms 6,676 KB
testcase_37	AC	15 ms 6,676 KB
testcase_38	AC	14 ms 6,676 KB
testcase_39	AC	17 ms 6,676 KB
testcase_40	AC	16 ms 6,676 KB
testcase_41	AC	17 ms 6,676 KB
testcase_42	AC	17 ms 6,676 KB
testcase_43	AC	17 ms 6,676 KB
testcase_44	AC	16 ms 6,676 KB
testcase_45	AC	16 ms 6,676 KB
testcase_46	AC	16 ms 6,676 KB
testcase_47	AC	18 ms 6,676 KB
testcase_48	AC	16 ms 6,676 KB
testcase_49	AC	16 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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==true
const bool test = true;
#define dump(x) cerr<<#x<<" : "<<(x)<< " "
#define dumpl(x) dump(x)<<endl
#define cerr_endl cerr<<endl
#else
const bool test = false;
#define dump(x) 
#define dumpl(x)
#define cerr_endl 
#endif

#else
const bool test = false;
#define dump(x) 
#define dumpl(x)
#endif

int 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, 1
int 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 template

struct 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 Player_x = 0, Player_y = 0;
int total_building = 0;
int total_store = 0;


//int get_buy_cnt() {
//  int a = total_building * 30 / 1000;
//  dumpl(a);
//  // 1000 -> 5
//  // 100 -> 20
//  // (1000) -> (15)
//  int b = max(5ll, (30 - a));
//  dumpl(b);
//
//  return b;
//}

int get_buy_cnt() {
  int a = total_building * 300 / 1000;
  int b = max(5ll, (30 - (int)pow(a, 1.5)));
  dumpl(b);

  return b;
}


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] += get_buy_cnt();
			rep(k, get_buy_cnt()) {
				print_ans(make_pair(2, to_string(bomb[bomb_id].original_id)));
			}

			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)));
  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] < get_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);

  player_move(W / 2, H / 2);
  for (int i = 0; i < m; i++) {
    int C, L;
    cin >> C >> L;
    bomb[i].cost = C;
    bomb[i].original_id = i + 1;
    for (int j = 0; j < L; j++) {
      int a, b;
      cin >> a >> b;
      bomb[i].places.push_back(make_pair(a, b));
    }
  }
  for (int i = 0; i < m; i++) {
    dumpl(bomb[i].places.size());
	}

  sort(all(bomb));
  solve();
  cout << ans.size() << endl;
  for (pair<int, string> i : ans) {
    cout << i.first << " " << i.second << endl;
  }
  print_field();
  int tmp = 0;
}

yukicoder

結果

テストケース

ソースコード