結果

問題 No.5016 Worst Mayor
ユーザー ks2mks2m
提出日時 2023-04-29 15:29:45
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,788 ms / 2,000 ms
コード長 5,070 bytes
コンパイル時間 5,452 ms
コンパイル使用メモリ 76,856 KB
実行使用メモリ 79,744 KB
スコア 2,275,586,830
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 15:31:23
合計ジャッジ時間 97,099 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,788 ms
77,336 KB
testcase_01 AC 1,722 ms
77,848 KB
testcase_02 AC 1,749 ms
77,644 KB
testcase_03 AC 1,700 ms
77,212 KB
testcase_04 AC 1,716 ms
77,692 KB
testcase_05 AC 1,729 ms
77,496 KB
testcase_06 AC 1,767 ms
75,144 KB
testcase_07 AC 1,714 ms
77,868 KB
testcase_08 AC 1,739 ms
75,232 KB
testcase_09 AC 1,706 ms
75,432 KB
testcase_10 AC 1,716 ms
78,060 KB
testcase_11 AC 1,737 ms
77,232 KB
testcase_12 AC 1,749 ms
75,380 KB
testcase_13 AC 1,742 ms
74,936 KB
testcase_14 AC 1,709 ms
77,536 KB
testcase_15 AC 1,733 ms
78,112 KB
testcase_16 AC 1,706 ms
77,556 KB
testcase_17 AC 1,743 ms
77,736 KB
testcase_18 AC 1,731 ms
77,788 KB
testcase_19 AC 1,737 ms
77,688 KB
testcase_20 AC 1,711 ms
77,280 KB
testcase_21 AC 1,713 ms
77,616 KB
testcase_22 AC 1,731 ms
77,264 KB
testcase_23 AC 1,766 ms
74,668 KB
testcase_24 AC 1,735 ms
77,456 KB
testcase_25 AC 1,727 ms
78,052 KB
testcase_26 AC 1,721 ms
77,692 KB
testcase_27 AC 1,757 ms
77,524 KB
testcase_28 AC 1,733 ms
76,924 KB
testcase_29 AC 1,717 ms
76,072 KB
testcase_30 AC 1,737 ms
75,720 KB
testcase_31 AC 1,721 ms
77,108 KB
testcase_32 AC 1,719 ms
77,400 KB
testcase_33 AC 1,734 ms
79,744 KB
testcase_34 AC 1,709 ms
77,244 KB
testcase_35 AC 1,726 ms
77,568 KB
testcase_36 AC 1,712 ms
77,224 KB
testcase_37 AC 1,759 ms
77,496 KB
testcase_38 AC 1,723 ms
77,004 KB
testcase_39 AC 1,727 ms
75,612 KB
testcase_40 AC 1,737 ms
77,324 KB
testcase_41 AC 1,716 ms
78,128 KB
testcase_42 AC 1,715 ms
77,796 KB
testcase_43 AC 1,743 ms
75,804 KB
testcase_44 AC 1,706 ms
74,800 KB
testcase_45 AC 1,714 ms
75,852 KB
testcase_46 AC 1,726 ms
77,896 KB
testcase_47 AC 1,733 ms
77,592 KB
testcase_48 AC 1,743 ms
77,520 KB
testcase_49 AC 1,716 ms
75,844 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 boolean[] fixed = new boolean[W2];

	static int[] getCnts(boolean[][] x, boolean[][] y) {
		int[] ret = new int[N];
		for (int i = 0; i < N; i++) {
			Obj o = arr[i];
			if (o.ab == o.cd) {
				continue;
			}
			Arrays.fill(dist, Integer.MAX_VALUE);
			Arrays.fill(fixed, false);
			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 (fixed[cur.v]) {
					continue;
				}
				fixed[cur.v] = true;
				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;
						int add = (Math.abs(o.c - nx) + Math.abs(o.d - ny)) * 223;
						que.add(new Node(next, alt + add));
					}
				}
			}
			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