結果

問題 No.5016 Worst Mayor
ユーザー ks2mks2m
提出日時 2023-04-29 15:00:03
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 4,718 bytes
コンパイル時間 3,008 ms
コンパイル使用メモリ 77,224 KB
実行使用メモリ 97,068 KB
スコア 0
最終ジャッジ日時 2023-04-29 15:00:14
合計ジャッジ時間 9,126 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Main {
	static long startTime;
	static long limitTime = 18000;
	static long limitTime1;
	static int N, T;
	static int W = 14;
	static int W1 = 13;
	static int W2 = 196;
	static int W21 = 182;
	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 {
		startTime = System.currentTimeMillis();
		String[] sa = br.readLine().split(" ");
		N = Integer.parseInt(sa[0]);
		T = Integer.parseInt(sa[1]);
		limitTime1 = limitTime / T;

		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[W1][W];
		boolean[][] y = new boolean[W][W1];

		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;
			}
			long limit = startTime + limitTime1 * (t + 1);

			int max = 0;
			int maxdir = 0;
			int maxx = 0;
			int maxy = 0;
			Set<Integer> set = new HashSet<>();
			while (System.currentTimeMillis() < limit) {
				int r = (int) (Math.random() * W21);
				if (!set.add(r)) {
					continue;
				}
				{
					int i = r / W;
					int j = r % W;
					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;
				}
				{
					int i = r / W1;
					int j = r % W1;
					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;
		}
	}
}
0