結果
問題 | No.5016 Worst Mayor |
ユーザー |
![]() |
提出日時 | 2023-04-29 14:47:14 |
言語 | Java (openjdk 23) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,336 bytes |
コンパイル時間 | 2,599 ms |
コンパイル使用メモリ | 75,580 KB |
実行使用メモリ | 94,248 KB |
スコア | 0 |
最終ジャッジ日時 | 2023-04-29 14:47:24 |
合計ジャッジ時間 | 9,103 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.PriorityQueue;public class Main {static int N, T;static int W = 14;static int W2 = 196;static Obj[] arr;static int[] dx = {1, 0, -1, 0};static int[] dy = {0, 1, 0, -1};public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));init(br);solve(br);}static void init(BufferedReader br) throws Exception {String[] sa = br.readLine().split(" ");N = Integer.parseInt(sa[0]);T = Integer.parseInt(sa[1]);arr = new Obj[N];for (int i = 0; i < N; i++) {sa = br.readLine().split(" ");Obj o = new Obj();o.a = Integer.parseInt(sa[0]) - 1;o.b = Integer.parseInt(sa[1]) - 1;o.c = Integer.parseInt(sa[2]) - 1;o.d = Integer.parseInt(sa[3]) - 1;o.ab = toInt(o.a, o.b);o.cd = toInt(o.c, o.d);arr[i] = o;}}static int solve(BufferedReader br) throws Exception {int numGoal = 20;int cost = (int) (10000000 / Math.sqrt(numGoal));boolean[][] x = new boolean[W - 1][W];boolean[][] y = new boolean[W][W - 1];for (int t = 0; t < T; t++) {String[] sa = br.readLine().split(" ");int money = Integer.parseInt(sa[0]);int num = Integer.parseInt(sa[1]);if (num < numGoal) {System.out.println(2);continue;}if (money < cost) {System.out.println(3);continue;}int max = 0;int maxdir = 0;int maxx = 0;int maxy = 0;for (int i = 0; i < x.length; i++) {for (int j = 0; j < x[0].length; j++) {if (x[i][j]) {continue;}x[i][j] = true;int[] cnts = getCnts(x, y);int sum = 0;for (int k = 0; k < N; k++) {sum += cnts[k];}if (sum > max) {max = sum;maxdir = 1;maxx = i;maxy = j;}x[i][j] = false;}}for (int i = 0; i < y.length; i++) {for (int j = 0; j < y[0].length; j++) {if (y[i][j]) {continue;}y[i][j] = true;int[] cnts = getCnts(x, y);int sum = 0;for (int k = 0; k < N; k++) {sum += cnts[k];}if (sum > max) {max = sum;maxdir = 2;maxx = i;maxy = j;}y[i][j] = false;}}StringBuilder sb = new StringBuilder();sb.append(1);sb.append(' ').append(maxx + 1);sb.append(' ').append(maxy + 1);if (maxdir == 1) {x[maxx][maxy] = true;sb.append(' ').append(maxx + 2);sb.append(' ').append(maxy + 1);} else {y[maxx][maxy] = true;sb.append(' ').append(maxx + 1);sb.append(' ').append(maxy + 2);}System.out.println(sb.toString());}int score = 0;return score;}static int[] dist = new int[W2];static int[] getCnts(boolean[][] x, boolean[][] y) {int[] ret = new int[N];for (int i = 0; i < N; i++) {Obj o = arr[i];Arrays.fill(dist, Integer.MAX_VALUE);dist[o.ab] = 0;PriorityQueue<Node> que = new PriorityQueue<Node>();Node first = new Node(o.ab, 0);que.add(first);while (!que.isEmpty()) {Node cur = que.poll();if (cur.v == o.cd) {break;}if (cur.d > dist[cur.v]) {continue;}int cx = cur.v / W;int cy = cur.v % W;for (int k = 0; k < 4; k++) {int nx = cx + dx[k];int ny = cy + dy[k];if (nx < 0 || W <= nx || ny < 0 || W <= ny) {continue;}int alt = dist[cur.v];if (k == 0) {alt += x[cx][cy] ? 223 : 1000;} else if (k == 1) {alt += y[cx][cy] ? 223 : 1000;} else if (k == 2) {alt += x[nx][cy] ? 223 : 1000;} else {alt += y[cx][ny] ? 223 : 1000;}int next = toInt(nx, ny);if (alt < dist[next]) {dist[next] = alt;que.add(new Node(next, alt));}}}int d = dist[o.cd];int cnt = 0;while (d >= 0) {if (d % 1000 == 0) {break;}d -= 223;cnt++;}ret[i] = cnt;}return ret;}static int toInt(int x, int y) {return x * W + y;}static class Obj {int a, b, c, d, ab, cd, cnt;}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;}}}