結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 EvbCFfp1XB
|
| 提出日時 | 2023-04-29 16:08:38 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,824 bytes |
| コンパイル時間 | 2,816 ms |
| コンパイル使用メモリ | 80,532 KB |
| 実行使用メモリ | 79,656 KB |
| スコア | 491,835,816 |
| 平均クエリ数 | 247.68 |
| 最終ジャッジ日時 | 2023-04-29 16:09:16 |
| 合計ジャッジ時間 | 29,402 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 WA * 47 |
ソースコード
import java.util.PriorityQueue;import java.util.Scanner;public final class Main {private static final int S = 14;private int N;private int T;private int[] A;private int[] B;private int[] C;private int[] D;static final Watch watch = new Watch();static final XorShift rng = new XorShift(System.nanoTime());public static final void main(final String[] args) {new Main().run();}private void run() {try (final Scanner in = new Scanner(System.in)) {N = in.nextInt();watch.init();T = in.nextInt();A = new int[N];B = new int[N];C = new int[N];D = new int[N];for (int i = 0; i < N; i++) {A[i] = in.nextInt() - 1;B[i] = in.nextInt() - 1;C[i] = in.nextInt() - 1;D[i] = in.nextInt() - 1;}int[][] counts = new int[2 * S][2 * S];for (int r = 0; r < 2 * S; r++) {for (int c = 0; c < 2 * S; c++) {counts[r][c]++;}}// for (int i = 0; i < N; i++) {// int minR = 2 * Math.min(A[i], C[i]);// int maxR = 2 * Math.max(A[i], C[i]);// int minC = 2 * Math.min(B[i], D[i]);// int maxC = 2 * Math.max(B[i], D[i]);// for (int r = minR; r <= maxR; r++) {// for (int c = minC; c <= maxC; c++) {// counts[r][c]++;// }// }// }PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>();for (int r = 0; r < 2 * S; r++) {for (int c = 0; c < 2 * S; c++) {if ((r + c) % 2 == 0) {continue;}final int min = 4;final int max = 22;final int center = 14;final int coef = ((r == center) && c >= min && c <= max) || ((c == min || c == max) && r >= min && r <= max) ? 10000 : 100;pq.add(new Pair<Integer, Integer>((coef * -counts[r][c]) + (rng.nextInt(100)), (r << 16) | (c)));}}int num_higways = 0;int prev_capital = (int) 1e6;int prev_action = 0;for (int t = 0; t < T; t++) {int capital = in.nextInt();int collaborators = in.nextInt();if (capital < 0 && collaborators < 0) {break;}int highway_revenue = capital - prev_capital + (prev_action == 3 ? -50000 : 0);int highway_cost = (int) (1 + 1e7 / Math.sqrt(collaborators));if (t < 21) {int action = 2;System.out.println(action);System.out.flush();prev_capital = capital;prev_action = action;continue;}final boolean build_highway_is_better = num_higways == 0 || (highway_revenue / num_higways) * (num_higways + 1) * (T - 1 - t) -highway_cost > highway_revenue * (T - 1 - t);if (capital >= highway_cost && build_highway_is_better) {num_higways++;int action = 1;int v = pq.poll().second.intValue();int r = v >>> 16;int c = v & ((1 << 16) - 1);if (r % 2 == 0) {assert c % 2 == 1;int r2 = 1 + r / 2;int c2 = 1 + (c - 1) / 2;int c3 = 1 + (c + 1) / 2;System.out.println(action + " " + r2 + " " + c2 + " " + r2 + " " + c3);System.out.flush();prev_capital = capital;prev_action = action;continue;} else {assert c % 2 == 0;int r2 = 1 + (r - 1) / 2;int r3 = 1 + (r + 1) / 2;int c2 = 1 + c / 2;System.out.println(action + " " + r2 + " " + c2 + " " + r3 + " " + c2);System.out.flush();prev_capital = capital;prev_action = action;continue;}}int action = 3;System.out.println(action);System.out.flush();prev_capital = capital;prev_action = action;}} catch (final Exception e) {e.printStackTrace();}}}class Watch {private long start;public Watch() {init();}public double getSecond() {return (System.nanoTime() - start) * 1e-9;}public void init() {init(System.nanoTime());}private void init(long start) {this.start = start;}public String getSecondString() {return toString(getSecond());}public static final String toString(double second) {if (second < 60) {return String.format("%5.2fs", second);} else if (second < 60 * 60) {int minute = (int) (second / 60);return String.format("%2dm%2ds", minute, (int) (second % 60));} else {int hour = (int) (second / (60 * 60));int minute = (int) (second / 60);return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));}}}class XorShift {private int w = 88675123;private int x = 123456789;private int y = 362436069;private int z = 521288629;public XorShift(long l) {x = (int) l;}public int nextInt() {final int t = x ^ (x << 11);x = y;y = z;z = w;w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));return w;}public long nextLong() {return ((long) nextInt() << 32) ^ (long) nextInt();}public double nextDouble() {return (nextInt() >>> 1) * 4.6566128730773926E-10;}public int nextInt(int n) {return (int) (n * nextDouble());}}class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {public T first;public S second;public Pair(T t, S s) {this.first = t;this.second = s;}private int hash = 0;@Overridepublic int hashCode() {if (hash == 0) {final int prime = 31;int result = 1;result = prime * result + ((first == null) ? 0 : first.hashCode());result = prime * result + ((second == null) ? 0 : second.hashCode());hash = result;}return hash;}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;Pair<T, S> other = (Pair<T, S>) obj;if (first == null) {if (other.first != null)return false;} else if (!first.equals(other.first))return false;if (second == null) {if (other.second != null)return false;} else if (!second.equals(other.second))return false;return true;}@Overridepublic int compareTo(Pair<T, S> o) {return first.compareTo(o.first);}}