結果

問題 No.5019 Hakai Project
ユーザー PechiPechi
提出日時 2023-11-19 19:42:13
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,527 ms / 3,000 ms
コード長 17,812 bytes
コンパイル時間 5,801 ms
コンパイル使用メモリ 291,064 KB
実行使用メモリ 22,912 KB
スコア 2,279,267,844
最終ジャッジ日時 2023-11-19 19:44:32
合計ジャッジ時間 139,462 ms
ジャッジサーバーID
(参考情報)
judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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, ngcnt, score;
array<set<pair<int, int>>, 2500> cnt;
array<array<int, 50>, 50> plan, subplan;
array<pair<double, int>, 20> priority;
array<array<pair<int,int>, 20>,2500> score_table;
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) {
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 (now_dist == -1)now_dist = 200;
score_table[convert(x, y)][i] = { pow(now_dist, 1.5),i };
if (dist > now_dist) {
dist = now_dist;
plan[y][x] = priority[i].second;
}
}
SORT(score_table[convert(x, y)]);
subplan[y][x] = plan[y][x];
if (dist == -1)dist = 100;
score[convert(x, y)] = pow(dist, 1.5);
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)].insert({ x,y });
}
}
}
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();
ngcnt[convert(x, y)] = 0;
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)].size() > 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)].erase({ x,y });
}
cost -= bomb[plan[y][x]].first;
plan[y][x] = -1;
--bomb_cnt;
}
}
for (int y = 0; y < n; ++y) {
for (int x = 0; x < n; ++x) {
ngcnt[convert(x, y)] = 0;
if (plan[y][x] == -1)continue;
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;
ngcnt[convert(x, y)] += ((cnt[convert(nx, ny)].size() == 1) && (t[convert(nx, ny)] == 1));
}
}
}
while (getTime() <= 2500) {
int x = xor128() % n, y = xor128() % n, z = 0;
if (plan[y][x] != -1)continue;
while (z != m) {
if (xor128() % 2)break;
++z;
}
score[convert(x, y)] = score_table[convert(x, y)][z].first;
subplan[y][x] = priority[score_table[convert(x, y)][z].second].second;
double now_score = score[convert(x, y)] + bomb[subplan[y][x]].first;
map<pair<int, int>, int> hitcnt;
priority_queue<pair<int, pair<int, int>>> er;
set<pair<int, int>> del;
for (auto &d : bomb[subplan[y][x]].second) {
int nx = x + d.first, ny = y + d.second;
if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
if (cnt[convert(nx, ny)].size() == 1 && t[convert(nx, ny)] == 1) {
for (auto &b : cnt[convert(nx, ny)]) {
hitcnt[{b.first, b.second}] += 1;
}
}
}
for (auto h : hitcnt) {
if (ngcnt[convert(h.first.first, h.first.second)] == h.second)er.push({ score[convert(h.first.first, h.first.second)],h.first });
}
for (auto &d : bomb[subplan[y][x]].second) {
int nx = x + d.first, ny = y + d.second;
if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
if (cnt[convert(nx, ny)].size() == 1 && (t[convert(nx, ny)] == 1)) {
int x2 = (cnt[convert(nx, ny)].begin())->first, y2 = (cnt[convert(nx, ny)].begin())->second;
--ngcnt[convert(x2, y2)];
}
if (cnt[convert(nx, ny)].size() == 0 && (t[convert(nx, ny)] == 1))++ngcnt[convert(x, y)];
cnt[convert(nx, ny)].insert({ x,y });
}
while (er.size() != 0) {
int c = er.top().first, x2 = er.top().second.first, y2 = er.top().second.second;
er.pop();
bool ok = 1;
for (auto &d : bomb[subplan[y2][x2]].second) {
int nx = x2 + d.first, ny = y2 + d.second;
if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
cnt[convert(nx, ny)].erase({ x2,y2 });
if (cnt[convert(nx, ny)].size() == 1 && (t[convert(nx, ny)] == 1)) {
int x3 = (cnt[convert(nx, ny)].begin())->first, y3 = (cnt[convert(nx, ny)].begin())->second;
++ngcnt[convert(x3, y3)];
}
if (cnt[convert(nx, ny)].size() == 0 && (t[convert(nx, ny)] == 1))ok = 0;
}
if (ok)now_score -= score[convert(x2, y2)] + bomb[plan[y2][x2]].first, del.insert({ x2,y2 });
else {
for (auto &d : bomb[subplan[y2][x2]].second) {
int nx = x2 + d.first, ny = y2 + d.second;
if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
if (cnt[convert(nx, ny)].size() == 1 && (t[convert(nx, ny)] == 1)) {
int x3 = (cnt[convert(nx, ny)].begin())->first, y3 = (cnt[convert(nx, ny)].begin())->second;
--ngcnt[convert(x3, y3)];
}
if (cnt[convert(nx, ny)].size() == 0 && (t[convert(nx, ny)] == 1))++ngcnt[convert(x2, y2)];
cnt[convert(nx, ny)].insert({ x2,y2 });
}
}
}
if (now_score < 0) {
for (auto p : del) {
cost -= bomb[plan[p.second][p.first]].first;
plan[p.second][p.first] = -1, --bomb_cnt;
}
plan[y][x] = subplan[y][x];
cost += bomb[plan[y][x]].first;
++bomb_cnt;
#ifdef DEBUG
cerr << bomb_cnt << " " << cost << " " << now_score << "\n";
#endif
}
else {
for (auto p : del) {
int x2 = p.first, y2 = p.second;
for (auto &d : bomb[subplan[y2][x2]].second) {
int nx = x2 + d.first, ny = y2 + d.second;
if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
if (cnt[convert(nx, ny)].size() == 1 && (t[convert(nx, ny)] == 1)) {
int x3 = (cnt[convert(nx, ny)].begin())->first, y3 = (cnt[convert(nx, ny)].begin())->second;
--ngcnt[convert(x3, y3)];
}
if (cnt[convert(nx, ny)].size() == 0 && (t[convert(nx, ny)] == 1))++ngcnt[convert(x2, y2)];
cnt[convert(nx, ny)].insert({ x2,y2 });
}
}
for (auto &d : bomb[subplan[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)].erase({ x,y });
if (cnt[convert(nx, ny)].size() == 1 && (t[convert(nx, ny)] == 1)) {
int x3 = (cnt[convert(nx, ny)].begin())->first, y3 = (cnt[convert(nx, ny)].begin())->second;
++ngcnt[convert(x3, y3)];
}
}
}
}
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()) <= 1000) {
double temp = 2 + 8 * ((1000.0 - time) / 1000.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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0