結果
問題 | No.5019 Hakai Project |
ユーザー |
![]() |
提出日時 | 2023-11-19 15:06:35 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.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 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#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#endifinline float getTime() {#ifdef DEBUGreturn duration_cast<milliseconds>(system_clock::now() - starttime).count() * 2.0;#elsereturn 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);}