結果

問題 No.5016 Worst Mayor
コンテスト
ユーザー ks2m
提出日時 2023-04-29 15:10:35
言語 Java
(openjdk 23)
結果
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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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