#929598 (C++17) No.5019 Hakai Project

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	Pechi
提出日時	2023-11-19 15:06:35
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,583 ms / 3,000 ms
コード長	13,060 bytes
コンパイル時間	5,369 ms
コンパイル使用メモリ	271,660 KB
実行使用メモリ	6,676 KB
スコア	1,927,934,534
最終ジャッジ日時	2023-11-19 15:08:06
合計ジャッジ時間	90,973 ms
ジャッジサーバーID （参考情報）	judge15 / judge13
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,583 ms 6,676 KB
testcase_01	AC	1,564 ms 6,676 KB
testcase_02	AC	1,568 ms 6,676 KB
testcase_03	AC	1,563 ms 6,676 KB
testcase_04	AC	1,566 ms 6,676 KB
testcase_05	AC	1,565 ms 6,676 KB
testcase_06	AC	1,562 ms 6,676 KB
testcase_07	AC	1,567 ms 6,676 KB
testcase_08	AC	1,561 ms 6,676 KB
testcase_09	AC	1,564 ms 6,676 KB
testcase_10	AC	1,563 ms 6,676 KB
testcase_11	AC	1,563 ms 6,676 KB
testcase_12	AC	1,565 ms 6,676 KB
testcase_13	AC	1,564 ms 6,676 KB
testcase_14	AC	1,569 ms 6,676 KB
testcase_15	AC	1,565 ms 6,676 KB
testcase_16	AC	1,567 ms 6,676 KB
testcase_17	AC	1,569 ms 6,676 KB
testcase_18	AC	1,561 ms 6,676 KB
testcase_19	AC	1,565 ms 6,676 KB
testcase_20	AC	1,563 ms 6,676 KB
testcase_21	AC	1,566 ms 6,676 KB
testcase_22	AC	1,570 ms 6,676 KB
testcase_23	AC	1,566 ms 6,676 KB
testcase_24	AC	1,568 ms 6,676 KB
testcase_25	AC	1,565 ms 6,676 KB
testcase_26	AC	1,561 ms 6,676 KB
testcase_27	AC	1,572 ms 6,676 KB
testcase_28	AC	1,575 ms 6,676 KB
testcase_29	AC	1,570 ms 6,676 KB
testcase_30	AC	1,557 ms 6,676 KB
testcase_31	AC	1,558 ms 6,676 KB
testcase_32	AC	1,562 ms 6,676 KB
testcase_33	AC	1,568 ms 6,676 KB
testcase_34	AC	1,561 ms 6,676 KB
testcase_35	AC	1,565 ms 6,676 KB
testcase_36	AC	1,558 ms 6,676 KB
testcase_37	AC	1,561 ms 6,676 KB
testcase_38	AC	1,553 ms 6,676 KB
testcase_39	AC	1,574 ms 6,676 KB
testcase_40	AC	1,558 ms 6,676 KB
testcase_41	AC	1,565 ms 6,676 KB
testcase_42	AC	1,565 ms 6,676 KB
testcase_43	AC	1,569 ms 6,676 KB
testcase_44	AC	1,566 ms 6,676 KB
testcase_45	AC	1,562 ms 6,676 KB
testcase_46	AC	1,570 ms 6,676 KB
testcase_47	AC	1,560 ms 6,676 KB
testcase_48	AC	1,566 ms 6,676 KB
testcase_49	AC	1,568 ms 6,676 KB

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

ソースコード

raw source code

#define _USE_MATH_DEFINES
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#include<unordered_map>
#include<random>
#include <array>
#include <complex>
#include<chrono>
using namespace std;
#define LP(I,S,G) for (long long int I = (S); I < (G); ++I)
#define IN(X) 	for (int in = 0; in < X.size(); in++)cin >> X[in]
#define OUT(X) 	for (int in = 0; in < X.size(); in++)cout << X[in]<<" "
#define SORT(X) sort((X).begin(), (X).end())
#define CSORT(X,Y) sort(X.begin(), X.end(),Y)
#define COPY(X,Y) copy(X.begin(), X.end(), Y.begin())
#define ALL(X,Y) for (auto (X) :(Y))
#define FULL(a)  (a).begin(),(a).end()
#define BFS(Q,S) for(Q.push(S);Q.size()!=0;Q.pop())
typedef long long int ll;
typedef unsigned long long int ull;
long long int M = 998244353;

chrono::system_clock::time_point starttime;
using namespace std::chrono;
#ifndef ONLINE_JUDGE
#define DEBUG
#endif

inline float getTime() {
#ifdef DEBUG
	return duration_cast<milliseconds>(system_clock::now() - starttime).count() * 2.0;
#else
	return duration_cast<milliseconds>(system_clock::now() - starttime).count();
#endif
}


int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };

ll MAX(ll A, ll B) { return ((A) > (B) ? (A) : (B)); }
ll MIN(ll A, ll B) { return ((A) < (B) ? (A) : (B)); }
inline long long int xor128() {
	static long long int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	long long int t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

inline int convert(int x, int y, int z = 50) {
	return x + y * z;
}

inline int get_dist(int fx, int fy, int tx, int ty) {
	return abs(fx - tx) + abs(fy - ty);
}

inline int get_dist(pair<int,int> f,pair<int,int> t) {
	return get_dist(f.first, f.second, t.first, t.second);
}



array<array<int, 50>, 50> set_bomb(array<string, 50>& a, array<pair<int, vector<pair<int, int>>>, 20>& bomb) {
	constexpr int n = 50, m = 20;
	array<int, 2500> t, cnt;
	array<array<int, 50>, 50> plan = { -1 };
	array<pair<double, int>, 20> priority;
	for (int i = 0; i < m; ++i) priority[i] = {- double(bomb[i].second.size() - bomb[i].first) / bomb[i].second.size(),i };
	SORT(priority);
	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < n; ++x) {
			cnt[convert(x, y)] = 0;
			if (a[y][x] != '.') t[convert(x, y)] = 1;
			else t[convert(x, y)] = 0;
		}
	}
	int cost = 0;
	priority_queue<pair<int, pair<int, int>>> pq;
	for (int x = 0; x < n; ++x) {
		for (int y = 0; y < n; ++y) {
			int dist = INT_MAX;
			plan[y][x] = priority[0].second;
			for (int i = 0; i < m; ++i) {
				int now_dist = -1;
				for (auto &d : bomb[priority[i].second].second) {
					int nx = x + d.first, ny = y + d.second;
					if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
					if (a[ny][nx] == '@')now_dist = max(now_dist, get_dist(x, y, nx, ny));
				}
				if (dist == -1)dist = INT_MAX;
				if (dist > now_dist) {
					dist = now_dist;
					plan[y][x] = priority[i].second;
				}
			}
			if (dist == -1)dist = 100;
			pq.push({ dist,{x,y} });
			cost += bomb[plan[y][x]].first;
			for (auto &d : bomb[plan[y][x]].second) {
				int nx = x + d.first, ny = y + d.second;
				if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
				++cnt[convert(nx, ny)];
			}
		}
	}
	int bomb_cnt = n * n;
	while (pq.size() != 0) {
		int x = pq.top().second.first, y = pq.top().second.second;
		bool ok = 1;
		pq.pop();
		for (auto &d : bomb[plan[y][x]].second) {
			int nx = x + d.first, ny = y + d.second;
			if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
			ok &= ((cnt[convert(nx, ny)] > 1) || (t[convert(nx, ny)] == 0));
		}
		if (ok) {
			for (auto &d : bomb[plan[y][x]].second) {
				int nx = x + d.first, ny = y + d.second;
				if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
				--cnt[convert(nx, ny)];
			}
			cost -= bomb[plan[y][x]].first;
			plan[y][x] = -1;
			--bomb_cnt;
		}
	}

	return plan;
}

vector<pair<int, int>> set_shopOrder(array<string, 50>& a) {
	constexpr int n = 50, m = 20;
	vector<pair<int, int>> point(1);
	int cnt = 1;
	point[0] = { 0,0 };
	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < n; ++x) {
			if (a[y][x] == '@')point.push_back({ x,y }), ++cnt;
		}
	}
	vector<int> dist(cnt*cnt);
	vector<pair<int, int>> result(cnt);
	vector<int> order(cnt);
	for (int u = 0; u < cnt; ++u) {
		order[u] = u;
		for (int v = 0; v < cnt; ++v) {
			dist[convert(u, v, cnt)] = abs(point[u].first - point[v].first) + abs(point[u].second - point[v].second);
		}
	}
	int score = 0;
	for (int i = 0; i < cnt-1; ++i)score += dist[convert(order[i], order[i + 1], cnt)];
	double time = getTime();
	while ((time=getTime()) <= 1500) {
		double temp = 2 + 8 * ((1500.0-time) / 1500.0);
		int a = xor128() % (cnt-1);
		int b = a + 1 + xor128() % (cnt-1 - a);
		int d = a + 1, c = b + 1;
		int cost;
		if (b == cnt-1) {
			cost = dist[convert(order[a], order[b], cnt)] - dist[convert(order[a], order[d], cnt)];
		}
		else {
			cost = dist[convert(order[a], order[b], cnt)] + dist[convert(order[c], order[d], cnt)]
				- (dist[convert(order[a], order[d], cnt)] + dist[convert(order[b], order[c], cnt)]);
		}
		if (xor128() % 10000 < exp(-cost / temp) * 10000) {
			score += cost;
			while (d < b) {
				swap(order[d], order[b]);
				++d, --b;
			}
		}
	}
	for (int i = 0; i < cnt; ++i) {
		result[i] = point[order[i]];
	}
	score = 0;
	for (int i = 0; i < cnt-1; ++i)score += dist[convert(order[i], order[i + 1], cnt)];
	return result;
}

int add_vertex(int v, vector<int>& g, vector<vector<int>>& dp, vector<pair<int, int>>& vertex, bool is_last = 0) {
	for (int i = 0; i < dp.size(); ++i)dp[i].resize(dp[i].size() * 2, INT_MAX);
	dp.emplace_back(vector<int>(dp[0].size(), INT_MAX));
	g.emplace_back(v);
	if (is_last)dp[dp.size() - 1][(1 << (dp.size() - 1))] = 0;
	for (int x = (1 << (g.size() - 1)); x < (1 << g.size()); ++x) {
		for (int i = 0; i < dp.size(); ++i) {
			if ((x&(1 << i)) == 0)continue;
			int y = (x ^ (1 << i));
			int cnt = 0;
			for (int k = 0; k < dp.size(); ++k) {
				cnt += ((y&(1 << k)) != 0);
			}
			for (int k = 0; k < dp.size(); ++k) {
				if ((y&(1 << k)) == 0)continue;
				if (dp[k][y] == INT_MAX)continue;
				dp[i][x] = min(dp[i][x], dp[k][y] + (int)pow(cnt+is_last, 2)*get_dist(vertex[g[i]], vertex[g[k]]));
			}
		}
	}
	if (!is_last)return dp[1][(1 << dp.size()) - 1];
	else return dp[0][(1 << dp.size()) - 1];
}

vector<pair<int, int>> restore_order(vector<int>& g, vector<vector<int>>& dp, vector<pair<int, int>>& vertex, bool is_last = 0) {
	int now = (!is_last);
	int x = (1 << dp.size()) - 1;
	vector<pair<int, int>> order;
	while (x != 0) {
		int y = (x ^ (1 << now));
		int cnt = 0;
		for (int k = 0; k < dp.size(); ++k) {
			cnt += ((y&(1 << k)) != 0);
		}
		order.emplace_back(vertex[g[now]]);
		for (int i = 0; i < dp.size(); ++i) {
			if ((y&(1 << i)) == 0)continue;
			if (dp[i][y] == LLONG_MAX)continue;
			if (dp[now][x] == dp[i][y] + (int)pow(cnt + is_last, 2)*get_dist(vertex[g[now]], vertex[g[i]])) {
				now = i;
				break;
			}
		}
		x = y;
	}
	return order;
}

void remove_vertex(vector<int>& g, vector<vector<int>>& dp) {
	g.pop_back();
	dp.pop_back();
	for (int i = 0; i < dp.size(); ++i)dp[i].resize(dp[i].size() / 2);
}


vector<array<int,3>> set_destroyOrder(vector<pair<int, int>>& shopOrder, array<array<int, 50>, 50>& bombPlan, array<string, 50>& a, array<pair<int, vector<pair<int, int>>>, 20>& bomb) {
	constexpr int n = 50, m = 20;
	int bomb_cnt = 0, shop_cnt = shopOrder.size();
	array<array<int, 50>, 50> id;
	vector<pair<int, int>> vertex(shopOrder.begin(), shopOrder.end());
	vector<int> cost_shop(shop_cnt);
	vector<vector<int>> g(shop_cnt);
	vector<vector<vector<int>>> dp(shop_cnt);
	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < n; ++x) {
			if (bombPlan[y][x] != -1)vertex.push_back({ x,y }), ++bomb_cnt;
			id[y][x] = -1;
		}
	}
	vector<vector<int>> cost_bomb(bomb_cnt, vector<int>(shop_cnt));
	vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> pq(bomb_cnt);
	vector<int> start(bomb_cnt, 1);
	vector<int> ok(bomb_cnt, 0);
	for (int i = 0; i < shop_cnt; ++i) {
		id[shopOrder[i].second][shopOrder[i].first] = i;
		if (i < shop_cnt-1) {
			cost_shop[i] = get_dist(shopOrder[i], shopOrder[i + 1]);
			dp[i] = vector<vector<int>>(2, vector<int>(4, INT_MAX));
			dp[i][0][1] = 0;
			dp[i][1][3] = cost_shop[i];
			g[i].emplace_back(i + 1);
			g[i].emplace_back(i);
		}
		else {
			cost_shop[i] = 0;
			dp[i] = vector<vector<int>>(1, vector<int>(2, INT_MAX));
			dp[i][0][1] = 0;
			g[i].emplace_back(i);
		}
	}
	for (int i = 0; i < bomb_cnt; ++i) {
		int x = vertex[shop_cnt + i].first, y = vertex[shop_cnt + i].second;
		for (auto &d : bomb[bombPlan[y][x]].second) {
			int nx = x + d.first, ny = y + d.second;
			if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
			if (a[ny][nx] == '@')start[i] = max(start[i], id[ny][nx]);
		}
		for (int k = start[i]; k < shop_cnt; ++k) {
			cost_bomb[i][k] = add_vertex(i + shop_cnt, g[k], dp[k], vertex, (k == shop_cnt-1)) - cost_shop[k];
			remove_vertex(g[k], dp[k]);
			pq[i].push({ cost_bomb[i][k],k });
		}
	}
	for (int now = 0; now < bomb_cnt; ++now) {
		int maxVal = INT_MIN, id = 0;
		for (int i = 0; i < bomb_cnt; ++i) {
			if (ok[i])continue;
			while (pq[i].top().first != cost_bomb[i][pq[i].top().second])pq[i].pop();
			if (maxVal < pq[i].top().first) {
				maxVal = pq[i].top().first;
				id = i;
			}
		}
		int tar = pq[id].top().second;
		cost_shop[tar] = add_vertex(id + shop_cnt, g[tar], dp[tar], vertex, (tar == shop_cnt-1));
		ok[id] = 1;
		for (int i = 0; i < bomb_cnt; ++i) {
			if (ok[i])continue;
			if (tar < start[i])continue;
			cost_bomb[i][tar] = add_vertex(i + shop_cnt, g[tar], dp[tar], vertex, (tar == shop_cnt-1)) - cost_shop[tar];
			remove_vertex(g[tar], dp[tar]);
			pq[i].push({ cost_bomb[i][tar],tar });
		}
	}
	vector<array<int, 3>> order;
	for (int i = 0; i < shop_cnt; ++i) {
		if (i != 0 && g[i].size() == 2 - (i == shop_cnt - 1)) continue;
		vector<pair<int, int>> new_order = restore_order(g[i], dp[i], vertex, (i == shop_cnt - 1));
		for (int k = 0; k < new_order.size() - (i != shop_cnt - 1); ++k) order.push_back({ new_order[k].first,new_order[k].second,(k == 0 && i != 0) });

	}
	return order;
}

string dijkstra(int sx, int sy, int gx, int gy, array<string, 50>& a) {
	constexpr int n = 50, m = 20;
	string t = "LDRU";
	vector<vector<int>> d(n, vector<int>(n, INT_MAX)), from(n, vector<int>(n, -1));
	d[gy][gx] = 0;
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
	pq.push({ 0,{gx,gy} });
	while (pq.size() != 0) {
		int c = pq.top().first, x = pq.top().second.first, y = pq.top().second.second;
		pq.pop();
		if (d[y][x] != c)continue;
		if (x == sx && y == sy)break;
		for (int i = 0; i < 4; ++i) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
			int nd = d[y][x] + 1 + (a[ny][nx] != '.');
			if (d[ny][nx] > nd) {
				d[ny][nx] = nd;
				from[ny][nx] = (i + 2) % 4;
				pq.push({ nd,{nx,ny} });
			}
		}
	}
	int x = sx, y = sy;
	string move = "";
	while (x != gx || y != gy) {
		int i = from[y][x];
		move += t[i];
		x += dx[i], y += dy[i];
	}
	return move;
}

vector<pair<int, pair<char, int>>> set_move(array<array<int, 50>, 50>& bombPlan, vector<array<int, 3>>& order, array<string, 50>& a, array<pair<int, vector<pair<int, int>>>, 20>& bomb) {
	constexpr int n = 50, m = 20;
	vector<pair<int, pair<char, int>>> result;
	for (int now = 0; now < order.size() - 1; ++now) {
		string move = dijkstra(order[now][0], order[now][1], order[now + 1][0], order[now + 1][1], a);
		for (auto act : move)result.push_back({ 1,{act,0} });
		if (order[now + 1][2]) {
			for (int i = now + 2; i < order.size(); ++i) {
				if (order[i][2])break;
				int x = order[i][0], y = order[i][1];
				result.push_back({ 2,{'.',bombPlan[y][x] + 1} });
			}
		}
		else {
			int x = order[now + 1][0], y = order[now + 1][1];
			result.push_back({ 3,{'.',bombPlan[y][x] + 1} });
			for (auto &d : bomb[bombPlan[y][x]].second) {
				int nx = x + d.first, ny = y + d.second;
				if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
				a[ny][nx] = '.';
			}
		}
	}
	return result;
}


int main(int argc, char* argv[]) {
	starttime = chrono::system_clock::now();
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	array<string,50> a;
	array<pair<int, vector<pair<int,int>>>,20> bomb;
	IN(a);
	for (int i = 0; i < m; ++i) {
		int c, l;
		cin >> c >> l;
		bomb[i].first = c;
		for (int k = 0; k < l; ++k) {
			int x, y;
			cin >> x >> y;
			bomb[i].second.push_back({ y,x });
		}
		sort(FULL(bomb[i].second));
	}
	vector<pair<int, int>> shopOrder = set_shopOrder(a);
	array<array<int, 50>, 50> plan = set_bomb(a, bomb);
	vector<array<int, 3>> order = set_destroyOrder(shopOrder, plan, a, bomb);
	vector<pair<int, pair<char, int>>> move = set_move(plan, order, a, bomb);
	cout << move.size() << "\n";
	for (auto act : move) {
		cout << act.first << " ";
		if (act.first == 1)cout << act.second.first << "\n";
		else cout << act.second.second << "\n";
	}
	exit(0);
}

yukicoder

結果

テストケース

ソースコード