結果

問題 No.5016 Worst Mayor
ユーザー EvbCFfp1XB
提出日時 2023-04-29 14:19:21
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 6,938 bytes
コンパイル時間 5,010 ms
コンパイル使用メモリ 89,908 KB
実行使用メモリ 79,380 KB
スコア 107,389,817
平均クエリ数 395.94
最終ジャッジ日時 2023-04-29 14:19:53
合計ジャッジ時間 29,741 ms
ジャッジサーバーID
(参考情報)
judge13 / judge14
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 48 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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 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;
}
pq.add(new Pair<Integer, Integer>(-counts[r][c], (r << 16) | (c)));
}
}
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);
double highway_cost = 1e7 / Math.sqrt(collaborators);
if (t < 21) {
int action = 2;
System.out.println(action);
System.out.flush();
prev_capital = capital;
prev_action = action;
continue;
}
if (capital >= highway_cost) {
int action = 1;
int v = pq.poll().second.intValue();
int r = v >>> 16;
int c = v & ((1 << 16) - 1);
if (r % 2 == 0) {
int r2 = r / 2;
int c2 = (c - 1) / 2;
int c3 = (c + 1) / 2;
System.out.println(action + " " + r2 + " " + c2 + " " + r2 + " " + c3);
System.out.flush();
prev_capital = capital;
prev_action = action;
continue;
} else {
int r2 = (r - 1) / 2;
int r3 = (r + 1) / 2;
int c2 = 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;
@Override
public 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;
}
@Override
public 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;
}
@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0