結果

問題 No.5016 Worst Mayor
ユーザー ks2mks2m
提出日時 2023-04-29 15:10:35
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,766 ms / 2,000 ms
コード長 4,866 bytes
コンパイル時間 2,824 ms
コンパイル使用メモリ 77,584 KB
実行使用メモリ 78,512 KB
スコア 2,410,255,990
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 15:12:10
合計ジャッジ時間 94,558 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,766 ms
76,432 KB
testcase_01 AC 1,727 ms
76,284 KB
testcase_02 AC 1,709 ms
76,392 KB
testcase_03 AC 1,721 ms
76,360 KB
testcase_04 AC 1,733 ms
76,424 KB
testcase_05 AC 1,737 ms
76,888 KB
testcase_06 AC 1,748 ms
76,756 KB
testcase_07 AC 1,717 ms
76,284 KB
testcase_08 AC 1,744 ms
76,712 KB
testcase_09 AC 1,705 ms
76,592 KB
testcase_10 AC 1,718 ms
76,708 KB
testcase_11 AC 1,713 ms
76,636 KB
testcase_12 AC 1,725 ms
75,992 KB
testcase_13 AC 1,727 ms
76,620 KB
testcase_14 AC 1,721 ms
76,408 KB
testcase_15 AC 1,716 ms
76,360 KB
testcase_16 AC 1,724 ms
76,440 KB
testcase_17 AC 1,729 ms
76,164 KB
testcase_18 AC 1,729 ms
76,424 KB
testcase_19 AC 1,716 ms
76,352 KB
testcase_20 AC 1,711 ms
78,512 KB
testcase_21 AC 1,755 ms
77,172 KB
testcase_22 AC 1,708 ms
76,468 KB
testcase_23 AC 1,727 ms
76,892 KB
testcase_24 AC 1,739 ms
76,260 KB
testcase_25 AC 1,751 ms
75,964 KB
testcase_26 AC 1,726 ms
76,172 KB
testcase_27 AC 1,712 ms
76,712 KB
testcase_28 AC 1,742 ms
76,192 KB
testcase_29 AC 1,716 ms
75,904 KB
testcase_30 AC 1,739 ms
74,808 KB
testcase_31 AC 1,734 ms
76,340 KB
testcase_32 AC 1,737 ms
76,488 KB
testcase_33 AC 1,714 ms
74,648 KB
testcase_34 AC 1,739 ms
77,216 KB
testcase_35 AC 1,719 ms
75,336 KB
testcase_36 AC 1,717 ms
75,972 KB
testcase_37 AC 1,722 ms
77,152 KB
testcase_38 AC 1,749 ms
76,480 KB
testcase_39 AC 1,747 ms
75,796 KB
testcase_40 AC 1,730 ms
76,844 KB
testcase_41 AC 1,717 ms
76,620 KB
testcase_42 AC 1,711 ms
77,272 KB
testcase_43 AC 1,745 ms
76,332 KB
testcase_44 AC 1,732 ms
74,628 KB
testcase_45 AC 1,730 ms
77,176 KB
testcase_46 AC 1,740 ms
76,544 KB
testcase_47 AC 1,722 ms
76,696 KB
testcase_48 AC 1,720 ms
75,956 KB
testcase_49 AC 1,729 ms
76,704 KB
権限があれば一括ダウンロードができます

ソースコード

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 = 1800;
	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];
		int preMax = 0;

		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;
				}
			}
			int val = (max - preMax) * 60 * (T - t);
			if (val - cost < 50000) {
				System.out.println(3);
				continue;
			}

			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());
			preMax = max;
		}
		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;
	}

	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