結果
| 問題 | 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; // TODOint 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;}}