結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 ks2m
|
| 提出日時 | 2023-11-18 18:02:29 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,190 ms / 3,000 ms |
| コード長 | 11,357 bytes |
| コンパイル時間 | 3,131 ms |
| コンパイル使用メモリ | 94,164 KB |
| 実行使用メモリ | 63,020 KB |
| スコア | 1,381,565,518 |
| 最終ジャッジ日時 | 2023-11-18 18:03:25 |
| 合計ジャッジ時間 | 56,199 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
public class Main {
static boolean readFile = false;
static int caseNum = 0;
static long startTime;
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
static int N, M;
static char[][] s;
static Bomb[] bbs;
public static void main(String[] args) throws Exception {
if (readFile) {
long score = solve(caseNum);
System.out.println(score);
} else {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
init(br);
solve(br);
br.close();
}
}
static long solve(int z) throws Exception {
StringBuilder sb = new StringBuilder();
sb.append(z);
while (sb.length() < 4) {
sb.insert(0, '0');
}
File file = new File("G:\\yuki\\008\\in\\" + sb.toString() + ".txt");
BufferedReader br = new BufferedReader(new FileReader(file));
init(br);
long res = solve(br);
br.close();
return res;
}
static void init(BufferedReader br) throws Exception {
startTime = System.currentTimeMillis();
String[] sa = br.readLine().split(" ");
N = Integer.parseInt(sa[0]);
M = Integer.parseInt(sa[1]);
s = new char[N][N];
for (int i = 0; i < N; i++) {
s[i] = br.readLine().toCharArray();
}
bbs = new Bomb[M];
for (int i = 0; i < M; i++) {
Bomb o = new Bomb();
sa = br.readLine().split(" ");
o.i = i + 1;
o.c = Integer.parseInt(sa[0]);
o.l = Integer.parseInt(sa[1]);
o.a = new int[o.l];
o.b = new int[o.l];
for (int j = 0; j < o.l; j++) {
sa = br.readLine().split(" ");
o.a[j] = Integer.parseInt(sa[0]);
o.b[j] = Integer.parseInt(sa[1]);
}
// o.v = (double) o.c / o.l;
bbs[i] = o;
}
}
static long solve(BufferedReader br) throws Exception {
// Arrays.sort(bbs, (o1, o2) -> Double.compare(o1.v, o2.v));
int[][] d = getDist();
int[][] v = new int[N][N];
List<Use> list = new ArrayList<>();
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if (s[x][y] != '.' && v[x][y] == 0) {
double bestCosp = 0;
Bomb bb = null;
int bx = 0;
int by = 0;
for (Bomb o : bbs) {
int tryCnt = 0;
for (int li = o.l - 1; li >= 0 && tryCnt < 300; li--) {
int cx = x - o.a[li];
if (cx < 0 || N <= cx) continue;
int cy = y - o.b[li];
if (cy < 0 || N <= cy) continue;
tryCnt++;
int cnt = 0;
for (int li2 = 0; li2 < o.l; li2++) {
int x2 = cx + o.a[li2];
if (x2 < 0 || N <= x2) continue;
int y2 = cy + o.b[li2];
if (y2 < 0 || N <= y2) continue;
if (s[x2][y2] != '.' && v[x2][y2] == 0) {
cnt++;
}
}
double cosp = (double) cnt / (o.c + d[cx][cy]);
if (cosp > bestCosp) {
bestCosp = cosp;
bb = o;
bx = cx;
by = cy;
}
}
}
for (int li2 = 0; li2 < bb.l; li2++) {
int x2 = bx + bb.a[li2];
if (x2 < 0 || N <= x2) continue;
int y2 = by + bb.b[li2];
if (y2 < 0 || N <= y2) continue;
v[x2][y2]++;
}
Use u = new Use();
u.b = bb;
u.ux = bx;
u.uy = by;
list.add(u);
}
}
}
// System.out.println(list.size());
Map<Integer, List<Use>> map = new HashMap<>();
for (Use u : list) {
setShop(u, d);
int k = toInt(u.sx, u.sy);
List<Use> list2 = map.get(k);
if (list2 == null) {
list2 = new ArrayList<>();
map.put(k, list2);
}
list2.add(u);
}
List<Event> evs = new ArrayList<>();
int cx = 0;
int cy = 0;
while (!map.isEmpty()) {
int bestk = -1;
int bestd = 100000000;
for (int k : map.keySet()) {
int nx = k / N;
int ny = k % N;
int dist = Math.abs(nx - cx) + Math.abs(ny - cy);
if (dist < bestd) {
bestd = dist;
bestk = k;
}
}
List<Use> list2 = map.get(bestk);
for (Use u : list2) {
Event e = new Event();
e.t = 2;
e.x = u.sx;
e.y = u.sy;
e.b = u.b;
evs.add(e);
}
for (Use u : list2) {
Event e = new Event();
e.t = 3;
e.x = u.ux;
e.y = u.uy;
e.b = u.b;
evs.add(e);
}
cx = list2.get(list2.size() - 1).ux;
cy = list2.get(list2.size() - 1).uy;
map.remove(bestk);
}
Set<Integer> shop = new HashSet<>();
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if (s[x][y] == '@') {
shop.add(toInt(x, y));
}
}
}
int size = evs.size();
for (int i = 0; i < size; i++) {
Event e = evs.get(i);
if (e.t == 3) {
for (int j = 0; j < e.b.l; j++) {
int x = e.x + e.b.a[j];
if (x < 0 || N <= x) continue;
int y = e.y + e.b.b[j];
if (y < 0 || N <= y) continue;
shop.remove(toInt(x, y));
}
Event pres = null;
int prei = -1;
for (int j = i - 1; j >= 0; j--) {
Event e2 = evs.get(j);
if (e2.t == 2) {
pres = e2;
prei = j;
break;
}
}
for (int j = i + 1; j < size; j++) {
Event e2 = evs.get(j);
if (e2.t == 2) {
int based = Math.abs(pres.x - e2.x) + Math.abs(pres.y - e2.y);
int p = toInt(e2.x, e2.y);
if (!shop.contains(p)) {
int bp = -1;
int bestd = 100000000;
for (int sp : shop) {
int sx = sp / N;
int sy = sp % N;
int sd = Math.abs(sx - e2.x) + Math.abs(sy - e2.y);
if (sd < bestd) {
bestd = sd;
bp = sp;
}
}
if (bestd <= based) {
e2.x = bp / N;
e2.y = bp % N;
} else {
evs.remove(j);
e2.x = pres.x;
e2.y = pres.y;
evs.add(prei, e2);
i++;
}
}
}
}
}
}
List<String> ans = new ArrayList<>();
cx = 0;
cy = 0;
for (Event e : evs) {
if (cx != e.x || cy != e.y) {
move(cx, cy, e.x, e.y, ans);
cx = e.x;
cy = e.y;
}
ans.add(e.t + " " + e.b.i);
}
PrintWriter pw = new PrintWriter(System.out);
pw.println(ans.size());
for (String str : ans) {
pw.println(str);
}
pw.flush();
// System.out.println((System.currentTimeMillis() - startTime) + "ms");
long score = 0;
// score = score(ans);
return score;
}
static void move(int sx, int sy, int tx, int ty, List<String> ans) {
int x1 = Math.min(sx, tx);
int x2 = Math.max(sx, tx);
int y1 = Math.min(sy, ty);
int y2 = Math.max(sy, ty);
int h = x2 - x1 + 1;
int w = y2 - y1 + 1;
char[][] s2 = new char[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
s2[i][j] = s[x1 + i][y1 + j];
}
}
int[][] d = new int[h][w];
int[][] pre = new int[h][w];
PriorityQueue<Node> que = new PriorityQueue<Node>();
for (int i = 0; i < h; i++) {
Arrays.fill(d[i], 100000000);
Arrays.fill(pre[i], -1);
}
d[sx - x1][sy - y1] = 0;
que.add(new Node(toInt(sx - x1, sy - y1), 0));
int gx = tx - x1;
int gy = ty - y1;
while (!que.isEmpty()) {
Node cur = que.poll();
int cx = cur.v / N;
int cy = cur.v % N;
if (cx == gx && cy == gy) {
break;
}
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx < 0 || h <= nx || ny < 0 || w <= ny) {
continue;
}
int alt = d[cx][cy];
if (s[nx][ny] == '.') {
alt++;
} else {
alt += 2;
}
if (alt < d[nx][ny]) {
d[nx][ny] = alt;
pre[nx][ny] = cur.v;
que.add(new Node(toInt(nx, ny), alt));
}
}
}
List<Integer> route = new ArrayList<>();
route.add(toInt(gx, gy));
int cx = gx;
int cy = gy;
while (pre[cx][cy] != -1) {
int v = pre[cx][cy];
cx = v / N;
cy = v % N;
route.add(toInt(cx, cy));
}
for (int i = route.size() - 1; i > 0; i--) {
int v1 = route.get(i);
int v1x = v1 / N;
int v1y = v1 % N;
int v2 = route.get(i - 1);
int v2x = v2 / N;
int v2y = v2 % N;
if (v1x == v2x) {
if (v1y < v2y) {
ans.add("1 R");
} else {
ans.add("1 L");
}
} else {
if (v1x < v2x) {
ans.add("1 D");
} else {
ans.add("1 U");
}
}
}
}
static void setShop(Use u, int[][] d) {
int cx = u.ux;
int cy = u.uy;
while (s[cx][cy] != '@') {
int best = 100000000;
int bi = -1;
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx < 0 || N <= nx || ny < 0 || N <= ny) {
continue;
}
if (d[nx][ny] < best) {
best = d[nx][ny];
bi = i;
}
}
cx = cx + dx[bi];
cy = cy + dy[bi];
}
u.sx = cx;
u.sy = cy;
}
static int[][] getDist() {
int[][] d = new int[N][N];
PriorityQueue<Node> que = new PriorityQueue<Node>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (s[i][j] == '@') {
que.add(new Node(toInt(i, j), 0));
} else {
d[i][j] = 100000000;
}
}
}
int sd = 16; // TODO
int sd2 = sd * 2;
while (!que.isEmpty()) {
Node cur = que.poll();
int cx = cur.v / N;
int cy = cur.v % N;
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx < 0 || N <= nx || ny < 0 || N <= ny) {
continue;
}
int alt = d[cx][cy];
if (s[nx][ny] == '.') {
alt += sd;
} else {
alt += sd2;
}
if (alt < d[nx][ny]) {
d[nx][ny] = alt;
que.add(new Node(toInt(nx, ny), alt));
}
}
}
return d;
}
static class Node implements Comparable<Node> {
int v, d;
public Node(int v, int d) {
this.v = v;
this.d = d;
}
public int compareTo(Node o) {
return d - o.d;
}
}
static class Bomb {
int i, c, l;
int[] a, b;
// double v;
}
static class Use {
Bomb b;
int ux, uy, sx, sy;
}
static class Event {
int t, x, y;
Bomb b;
}
static int toInt(int x, int y) {
return x * N + y;
}
static long score(List<String> ans) {
long c = 0;
int cx = 0;
int cy = 0;
int b1 = 1;
int[] bs = new int[M];
for (int z = 0; z < ans.size(); z++) {
String str = ans.get(z);
String[] sa = str.split(" ");
int t = Integer.parseInt(sa[0]);
if (t == 1) {
if (sa[1].equals("U")) cx--;
if (sa[1].equals("D")) cx++;
if (sa[1].equals("L")) cy--;
if (sa[1].equals("R")) cy++;
if (cx < 0 || N <= cx || cy < 0 || N <= cy) {
throw new RuntimeException(cx + "," + cy);
}
if (s[cx][cy] == '.') {
c += b1 * b1;
} else {
c += b1 * b1 * 2;
}
} else {
int mi = Integer.parseInt(sa[1]) - 1;
Bomb bb = bbs[mi];
if (t == 2) {
if (s[cx][cy] != '@') {
throw new RuntimeException(cx + "," + cy);
}
bs[mi]++;
b1++;
c += bb.c;
} else {
if (bs[mi] <= 0) {
throw new RuntimeException(mi + " " + bs[mi]);
}
bs[mi]--;
b1--;
for (int i = 0; i < bb.l; i++) {
int x = cx + bb.a[i];
if (x < 0 || N <= x) continue;
int y = cy + bb.b[i];
if (y < 0 || N <= y) continue;
s[x][y] = '.';
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (s[i][j] != '.') {
for (int x = 0; x < N; x++) {
System.out.println(s[x]);
}
throw new RuntimeException();
}
}
}
long ret = Math.max(10, 1000000000000L / (10000 + c));
return ret;
}
}