結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 Yu_212
|
| 提出日時 | 2023-04-29 17:01:49 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,659 ms / 2,000 ms |
| コード長 | 28,276 bytes |
| コンパイル時間 | 5,877 ms |
| コンパイル使用メモリ | 106,728 KB |
| 実行使用メモリ | 87,056 KB |
| スコア | 20,517,831,870 |
| 平均クエリ数 | 400.00 |
| 最終ジャッジ日時 | 2023-04-29 17:07:05 |
| 合計ジャッジ時間 | 87,339 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
import java.io.*;import java.util.*;import java.util.concurrent.ThreadLocalRandom;import java.util.function.IntUnaryOperator;import java.util.function.LongUnaryOperator;import java.util.stream.Collectors;public class Main {static boolean isLocal;Random rand = new Random();In in = new In(System.in);PrintStream out = System.out;long inf = 0x1fffffffffffffffL;int iinf = 0x3fffffff;long startTime;public static final long[] TABLE = new long[364];public static final int[] COST = {0,10000000,7071067,5773502,5000000,4472135,4082482,3779644,3535533,3333333,3162277,3015113,2886751,2773500,2672612,2581988,2500000,2425356,2357022,2294157,2236067,2182178,2132007,2085144,2041241,2000000,1961161,1924500,1889822,1856953,1825741,1796053,1767766,1740776,1714985,1690308,1666666,1643989,1622214,1601281,1581138,1561737,1543033,1524985,1507556,1490711,1474419,1458649,1443375,1428571,1414213,1400280,1386750,1373605,1360827,1348399,1336306,1324532,1313064,1301889,1290994,1280368,1270001,1259881,1250000,1240347,1230914,1221694,1212678,1203858,1195228,1186781,1178511,1170411,1162476,1154700,1147078,1139605,1132277,1125087,1118033,1111111,1104315,1097642,1091089,1084652,1078327,1072112,1066003,1059997,1054092,1048284,1042572,1036951,1031421,1025978,1020620,1015346,1010152,1005037,1000000,995037,990147,985329,980580,975900,971285,966736,962250,957826,953462,949157,944911,940720,936585,932504,928476,924500,920574,916698,912870,909090,905357,901669,898026,894427,890870,887356,883883,880450,877058,873704,870388,867109,863868,860662,857492,854357,851256,848188,845154,842151,839181,836242,833333,830454,827605,824786,821994,819231,816496,813788,811107,808452,805822,803219,800640,798086,795557,793051,790569,788110,785674,783260,780868,778498,776150,773823,771516,769230,766964,764719,762492,760285,758098,755928,753778,751646,749531,747435,745355,743294,741249,739221,737209,735214,733235,731272,729324,727392,725476,723574,721687,719815,717958,716114,714285,712470,710669,708881,707106,705345,703597,701862,700140,698430,696733,695048,693375,691714,690065,688428,686802,685188,683585,681994,680413,678844,677285,675737,674199,672672,671156,669649,668153,666666,665190,663723,662266,660818,659380,657951,656532,655121,653720,652328,650944,649569,648203,646846,645497,644156,642824,641500,640184,638876,637576,636284,635000,633724,632455,631194,629940,628694,627455,626224,625000,623782,622572,621369,620173,618984,617802,616626,615457,614295,613139,611990,610847,609710,608580,607456,606339,605227,604122,603022,601929,600841,599760,598684,597614,596549,595491,594438,593390,592348,591312,590281,589255,588235,587220,586210,585205,584206,583211,582222,581238,580258,579284,578314,577350,576390,575435,574484,573539,572598,571661,570730,569802,568880,567961,567047,566138,565233,564332,563436,562543,561655,560772,559892,559016,558145,557278,556414,555555,554700,553848,553001,552157,551317,550481,549649,548821,547996,547175,546358,545544,544734,543928,543125,542326,541530,540738,539949,539163,538381,537603,536828,536056,535287,534522,533760,533001,532246,531494,530744,529998,529256,528516,527779,527046,526315,525588,524863,524142,523423,522708,521995,521286,520579,519875,519174,518475,517780,517087,516397,515710,515026,514344,513665,512989,512315,511644,510976,510310,509647,508986,508328,507673,507020,506369,505721,505076,504433,503792,503154,502518,501885,501254,500626,500000};public static final int S = 14;public static final int SS = 196;public static final int N = 3000;public static final int T = 400;int curTurn;int corCollabo = 1;int corMoney = 1000000;long solve(int seed) {startTime = System.currentTimeMillis();Arrays.setAll(TABLE, i -> rand.next());in();// 80 10 424367600// 80 20 450836500// 80 30 439329940// 80 50 416846380// 50 50 404948590// 70 50 416677250// 90 50 417352330// 100 50 402903920// 150 50 344831110int u1 = 80;State2 state = new State2();int nj = 0;int lastU = 0;Action next = null;if (!isLocal) {corMoney = in.nextInt();in.nextInt();}while (curTurn < T) {if (next == null) {for (Action ac : state.actions()) {ac.open();if (next == null || next.score < ac.score) {next = ac;}}}boolean c1 = corMoney >= COST[corCollabo];int cd = COST[corCollabo] - COST[corCollabo + 1];int ud = (next.opened.score - lastU) * 60;int e1 = !c1 ? -iinf : (T - curTurn) * ud - cd - 50000 - COST[corCollabo];int e2 = Math.max(1, u1 - nj) * cd - ud - 50000;int e3 = 50000 - cd - ud;// debug(e1, e2, e3);// debug(corMoney);if (e2 > e1 && e2 > e3) {corCollabo++;corMoney += 60 * lastU;ask2();} else if (c1 && e1 > e3) {// debug(corCollabo, COST[corCollabo], corMoney);lastU = next.opened.score;corMoney += 60 * lastU - COST[corCollabo];nj++;ask1(next.x, next.v);state = next.opened;next = null;} else {corMoney += 50000 + 60 * lastU;ask3();}}// int u2 = 50;// State2 state = new State2();// // State2 result = beamSearch(new State2(), trace, 10, 100000);// // debug(result.score);// if (!isLocal) {// corMoney = in.nextInt();// in.nextInt();// }// // int money = 1000000;// int lastU = 0;// int nj = 0;// for (int i = 1; i < u2; i++) {// corCollabo++;// ask2();// }// while (true) {// while (corMoney < COST[corCollabo]) {// corMoney += 50000 + 60 * lastU;// ask3();// }//// Action best = null;// for (Action next : state.actions()) {// next.open();// if (best == null || best.score < next.score) {// best = next;// }// }// state = best.opened;//// // debug(k++, pos(action.x), action.v, action.opened.score);// if ((best.opened.score - lastU) * 60 * (T - curTurn) < 900000) {// debug(nj);// break;// }//// debug((best.opened.score - lastU) * (T - curTurn));// lastU = best.opened.score;// corMoney += 60 * lastU - COST[corCollabo];// nj++;// ask1(best.x, best.v);// if (curTurn >= T) {// break;// }// }// while (curTurn < T) {// corMoney += 60 * lastU;// ask3();// }//// int u1 = 80;// int[] u2 = {30, 20};//// Trace trace = new Trace();// State2 result = greedy(new State2(), trace, u1);//// State2 result = beamSearch(new State2(), trace, 10, 100000);//// debug(result.score);// if (!isLocal) {// corMoney = in.nextInt();// in.nextInt();// }//// int money = 1000000;// int lastU = 0;// int nj = 0;// List<Action> actions = trace.trace(result.id);// for (Action action : actions) {// for (int i = 0; nj < u2.length && i < u2[nj]; i++) {// corCollabo++;// ask2();// }// while (corMoney < COST[corCollabo]) {// corMoney += 50000 + 60 * lastU;// ask3();// }//// debug(k++, pos(action.x), action.v, action.opened.score);// if ((action.opened.score - lastU) * (T - curTurn) < 30000) {// break;// }// debug((action.opened.score - lastU) * (T - curTurn));// lastU = action.opened.score;// corMoney += 60 * lastU - COST[corCollabo];// nj++;// ask1(action.x, action.v);// if (curTurn >= T) {// break;// }// }// while (curTurn < T) {// corMoney += 60 * lastU;// ask3();// }return isLocal ? corMoney : 0;}int px(int x, boolean v) {return v ? x : x % S * S + x / S;}int py(int x, boolean v) {return v ? x + S : x % S * S + x / S + 1;}void ask1(int x, boolean v) {Pos px = pos(px(x, v));Pos py = pos(py(x, v));out.println("1 " + (px.x+1) + " " + (px.y+1) + " " + (py.x+1) + " " + (py.y+1));out.flush();curTurn++;if (!isLocal && curTurn < T) {corMoney = in.nextInt();in.nextInt();}}void ask2() {out.println(2);out.flush();curTurn++;if (!isLocal && curTurn < T) {corMoney = in.nextInt();in.nextInt();}}void ask3() {out.println(3);out.flush();curTurn++;if (!isLocal && curTurn < T) {corMoney = in.nextInt();in.nextInt();}}Pos[] fs, ts;void in() {Pos.init(S);in.nextInt();in.nextInt();fs = new Pos[N];ts = new Pos[N];for (int i = 0; i < N; i++) {int a = in.nextInt() - 1;int b = in.nextInt() - 1;int c = in.nextInt() - 1;int d = in.nextInt() - 1;fs[i] = pos(a, b);ts[i] = pos(c, d);}}Pos pos(int x, int y) {return Pos.instances[y * S + x];}Pos pos(int z) {return Pos.instances[z];}static class Pos implements Comparable<Pos> {static Pos[] instances = new Pos[SS];static Pos[] moved = new Pos[4 * SS];static void init(int n) {for (int i = 0; i < n * n; i++) {instances[i] = new Pos(i % n, i / n, i);}for (int i = 0; i < n * n; i++) {for (int d = 0; d < 4; d++) { // LURDint nx = i % n + (d - 1) % 2;int ny = i / n + (d - 2) % 2;if (0 <= nx && nx < n && 0 <= ny && ny < n) {moved[i * 4 + d] = instances[ny * n + nx];}}}}final int x, y, z;private Pos(int x, int y, int z) {this.x = x;this.y = y;this.z = z;}Pos moved(int d) {return moved[z * 4 + d];}int dist(Pos o) {return Math.abs(x - o.x) + Math.abs(y - o.y);}Pos[] neighbors() {Pos[] p = new Pos[4];int i = 0;if ((p[i] = moved(0)) != null) i++;if ((p[i] = moved(1)) != null) i++;if ((p[i] = moved(2)) != null) i++;if ((p[i] = moved(3)) != null) i++;return i == 4 ? p : Arrays.copyOf(p, i);}@Overridepublic int compareTo(Pos o) {return Integer.compare(z, o.z);}@Overridepublic boolean equals(Object o) {return o instanceof Pos && z == ((Pos)o).z;}@Overridepublic int hashCode() {return z;}@Overridepublic String toString() {return String.format("(%d, %d)", x, y);}}// class State {// int collabo;// int money;// BitSet vert;// BitSet hori;//// int constructCost() {// return COST[collabo];// }// }State2 initialState() {return new State2();}class State2 implements Comparable<State2> {int id;State2 prev;int score;long hash;BitSet vert; // |BitSet hori; // -int[] dist;int[] uses;State2() {this.id = -1;this.hash = 0;this.vert = new BitSet(SS);this.hori = new BitSet(SS);this.dist = new int[N];this.uses = new int[N];for (int i = 0; i < N; i++) {dist[i] = Math.abs(fs[i].x - ts[i].x) + Math.abs(fs[i].y - ts[i].y);}}State2(State2 prev) {this.id = prev.id;this.prev = prev;this.score = prev.score;this.hash = prev.hash;this.vert = (BitSet)prev.vert.clone();this.hori = (BitSet)prev.hori.clone();this.dist = prev.dist.clone();this.uses = prev.uses.clone();}boolean highway(Pos p, int d) {if ((d & 1) == 0) { // LURDreturn hori.get(p.z - (d>>1^1));} else {return vert.get(p.z - (d>>1^1) * S);}}int dist(int d, int u) {return d * 1000 - u * 777;}void update(int x, boolean v) {int px = px(x, v);int py = py(x, v);(v ? vert : hori).set(px);hash ^= TABLE[x + (v ? 182 : 0)];Deque<Pos> deque1 = new ArrayDeque<>();Deque<Pos> deque2 = new ArrayDeque<>();BitSet fromY = new BitSet(SS);deque1.add(pos(px));deque1.add(pos(py));deque2.add(pos(px));deque2.add(pos(py));fromY.set(py);int[] ds = new int[SS];int[] us = new int[SS];Arrays.fill(ds, 30);ds[px] = 0;ds[py] = 0;while (!deque1.isEmpty() || !deque2.isEmpty()) {Pos p1 = deque1.isEmpty() ? null : deque1.peekFirst();Pos p2 = deque2.isEmpty() ? null : deque2.peekFirst();Pos p;boolean h = p2 == null || p1 != null && dist(ds[p1.z], us[p1.z]) < dist(ds[p2.z], us[p2.z]);if (h) {p = deque1.removeFirst();} else {p = deque2.removeFirst();}for (int i = 0; i < 4; i++) {Pos q = p.moved(i);if (q == null || highway(p, i) != h) {continue;}int nd = ds[p.z] + 1;int nu = us[p.z] + (h ? 1 : 0);if (dist(ds[q.z], us[q.z]) > dist(nd, nu)) {ds[q.z] = nd;us[q.z] = nu;fromY.set(q.z, fromY.get(p.z));deque1.addLast(q);deque2.addLast(q);}}}for (int i = 0; i < N; i++) {if (fromY.get(fs[i].z) == fromY.get(ts[i].z)) {continue;}int nd = ds[fs[i].z] + ds[ts[i].z] + 1;int nu = us[fs[i].z] + us[ts[i].z] + 1;if (dist(dist[i], uses[i]) > dist(nd, nu)) {score += nu - uses[i];dist[i] = nd;uses[i] = nu;}}}static int[] ord = new int[182];static {Arrays.setAll(ord, i -> i);}List<Action> actions() {List<Action> nexts = new ArrayList<>();for (int ii = 0; ii < 60; ii++) {int j = ii + rand.next(182 - ii);int i = ord[j];ord[j] = ord[ii];ord[ii] = i;if (!vert.get(i)) {nexts.add(new Action(this, hash ^ TABLE[i + 182], i, true));}if (!hori.get(i)) {nexts.add(new Action(this, hash ^ TABLE[i], i, false));}}return nexts;}void advance(Trace trace, Action action) {hash = action.hash;score = action.score;id = trace.add(action, id);}State2 copy() {return new State2(this);}@Overridepublic int compareTo(State2 o) {return Integer.compare(score, o.score);}}class Action implements Comparable<Action> {State2 prev;State2 opened;long hash;int score;int x;boolean v;Action(State2 prev, long hash, int x, boolean v) {this.prev = prev;this.hash = hash;this.x = x;this.v = v;}void open() {opened = prev.copy();opened.update(x, v);score = opened.score;}@Overridepublic int compareTo(Action o) {return Integer.compare(o.score, score);}}static class Trace {List<Action> log = new ArrayList<>();List<Integer> prev = new ArrayList<>();int add(Action action, int pi) {log.add(action);prev.add(pi);return log.size() - 1;}List<Action> trace(int id) {List<Action> actions = new ArrayList<>();while (id != -1) {actions.add(log.get(id));id = prev.get(id);}Collections.reverse(actions);return actions;}Action first(int id) {Action first = null;while (id != -1) {first = log.get(id);id = prev.get(id);}return first;}void clear() {log.clear();prev.clear();}}State2 beamSearch(State2 initialState, Trace trace, int beamWidth, long timeLimit, int maxTurn) {long[] hashes = new long[1 << 20];initialState.id = -1;State2[] beam = {initialState};State2 best = null;for (int turn = 1; ; turn++) {boolean sorted = false;int numCand = 0;Action[] cand = new Action[beamWidth * 2];for (State2 state : beam) {if (state == null) {break;}for (Action action : state.actions()) {int key = (int)(action.hash & 0xfffff);if (hashes[key] != action.hash) {hashes[key] = action.hash;action.open();if (sorted && cand[beamWidth - 1].score > action.score) {continue;}cand[numCand++] = action;if (numCand == cand.length) {Arrays.sort(cand, Comparator.reverseOrder());numCand = beamWidth;sorted = true;}}}}Arrays.sort(cand);int size = Math.min(beamWidth, numCand);State2[] next = new State2[size];int j = 0;State2 found = null;for (int i = 0; i < numCand && j < size; i++) {Action action = cand[i];State2 copy = action.opened;copy.advance(trace, action);if (best == null || best.score < copy.score) {best = copy;}if (turn == maxTurn) {if (found == null || found.score < copy.score) {found = copy;}continue;}next[j++] = copy;}if (found != null) {return found;}if (j == 0 || elapsed(timeLimit)) {throw new RuntimeException();}beam = next;}}State2 greedy(State2 state, Trace trace, int maxTurn) {state.id = -1;for (int turn = 1; ; turn++) {Action best = null;for (Action next : state.actions()) {next.open();if (best == null || best.score < next.score) {best = next;}}state = best.opened;state.advance(trace, best);if (turn == maxTurn) {return state;}}}static void debug(Object... args) {if (!isLocal) {return;}if (args == null || args.getClass() != Object[].class) {args = new Object[] {args};}System.err.println(Arrays.stream(args).map(obj -> {Class<?> clazz = obj == null ? null : obj.getClass();return clazz == byte[].class ? Arrays.toString((byte[])obj) :clazz == short[].class ? Arrays.toString((short[])obj) :clazz == int[].class ? Arrays.toString((int[])obj) :clazz == long[].class ? Arrays.toString((long[])obj) :clazz == char[].class ? Arrays.toString((char[])obj) :clazz == float[].class ? Arrays.toString((float[])obj) :clazz == double[].class ? Arrays.toString((double[])obj) :clazz == boolean[].class ? Arrays.toString((boolean[])obj) :obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :String.valueOf(obj);}).collect(Collectors.joining(" ")));}long elapsed() {return (long)((System.currentTimeMillis() - startTime) * (isLocal ? 1.7 : 1));}boolean elapsed(long timeLimit) {return elapsed() >= timeLimit;}public static void main(String[] args) {new Main().solve(0);}static class BinarySearchTree<E extends Comparable<E>> implements Iterable<E> {private final int n;private final Object[] a;private int size;public BinarySearchTree(int n) {this.n = n;this.a = new Object[n];}public int size() {return size;}public void add(E element) {if (size < n) {int i = size++;while (i > 0) {int parent = (i - 1) / 2;if (get(parent).compareTo(element) <= 0) {break;}a[i] = a[parent];i = parent;}a[i] = element;} else if (n > 0 && get(0).compareTo(element) < 0) {int i = 0;while (i * 2 + 1 < n) {int child = i * 2 + 1;if (child + 1 < n && get(child).compareTo(get(child + 1)) > 0) {child++;}if (get(child).compareTo(element) >= 0) {break;}a[i] = a[child];i = child;}a[i] = element;}}@SuppressWarnings("unchecked")private E get(int index) {return (E)a[index];}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {private int i = 0;@Overridepublic boolean hasNext() {return i < size;}@Overridepublic E next() {return get(i++);}};}}static class Random {private long x, y, z, w;Random() {this(ThreadLocalRandom.current().nextLong());}Random(long seed) {this.x = seed;for (int i = 0; i < 20; i++) {rand();}}private long rand() {long t = x ^ (x << 11);x = y;y = z;z = w;w = w ^ (w >>> 19) ^ t ^ (t >>> 8);return x & 0x7fffffff;}long next() {return rand() << 31 | rand();}int next(int n) {return (int)(rand() % n);}int next(int l, int r) {return (int)(rand() % (r - l) + l);}double nextDouble() {return rand() / 2147483647.0;}}static class In {private final BufferedReader reader;private StringTokenizer tokenizer;In(InputStream input) {this.reader = new BufferedReader(new InputStreamReader(input), 0x10000);}String next() {try {while (tokenizer == null || !tokenizer.hasMoreTokens()) {tokenizer = new StringTokenizer(reader.readLine());}} catch (IOException ignored) {}return tokenizer.nextToken();}int nextInt() {return Integer.parseInt(next());}long nextLong() {return Long.parseLong(next());}double nextDouble() {return Double.parseDouble(next());}char[] nextCharArray() {return next().toCharArray();}String[] nextStringArray(int n) {String[] s = new String[n];for (int i = 0; i < n; i++) {s[i] = next();}return s;}char[][] nextCharGrid(int n, int m) {char[][] a = new char[n][m];for (int i = 0; i < n; i++) {a[i] = next().toCharArray();}return a;}int[] nextIntArray(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = nextInt();}return a;}int[] nextIntArray(int n, IntUnaryOperator op) {int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = op.applyAsInt(nextInt());}return a;}int[][] nextIntMatrix(int h, int w) {int[][] a = new int[h][w];for (int i = 0; i < h; i++) {a[i] = nextIntArray(w);}return a;}long[] nextLongArray(int n) {long[] a = new long[n];for (int i = 0; i < n; i++) {a[i] = nextLong();}return a;}long[] nextLongArray(int n, LongUnaryOperator op) {long[] a = new long[n];for (int i = 0; i < n; i++) {a[i] = op.applyAsLong(nextLong());}return a;}long[][] nextLongMatrix(int h, int w) {long[][] a = new long[h][w];for (int i = 0; i < h; i++) {a[i] = nextLongArray(w);}return a;}List<List<Integer>> nextEdges(int n, int m, boolean directed) {List<List<Integer>> res = new ArrayList<>();for (int i = 0; i < n; i++) {res.add(new ArrayList<>());}for (int i = 0; i < m; i++) {int u = nextInt() - 1;int v = nextInt() - 1;res.get(u).add(v);if (!directed) {res.get(v).add(u);}}return res;}}}