結果
| 問題 | No.5020 Averaging |
| ユーザー |
 ks2m
|
| 提出日時 | 2024-02-25 15:21:56 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 877 ms / 1,000 ms |
| コード長 | 8,519 bytes |
| コンパイル時間 | 3,968 ms |
| コンパイル使用メモリ | 96,712 KB |
| 実行使用メモリ | 74,092 KB |
| スコア | 36,332,974 |
| 最終ジャッジ日時 | 2024-02-25 15:22:48 |
| 合計ジャッジ時間 | 50,805 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge10 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
import java.io.BufferedReader;import java.io.File;import java.io.FileReader;import java.io.InputStreamReader;import java.io.PrintWriter;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;import java.util.PriorityQueue;public class Main {static boolean batch = false;static boolean readFile = false;static int caseNum = 1;static long limitTime = 800;static int queCap = 40;static int nextNum = 40;static long endTime;static long g = 500000000000000000L;static int T = 50;static int N;static long[] a, b;static List<Integer> order;public static void main(String[] args) throws Exception {if (batch) {readFile = true;}if (readFile) {if (batch) {long tl = 1000; // TODOlong tw = tl - 200;long total = 0;int bidx = 0;long best = 0;int widx = 0;long worst = 1000000000000000000L;int re = 0;int tle = 0;for (int z = 1; z <= 50; z++) {try {long st = System.currentTimeMillis();long score = solve(z);long time = System.currentTimeMillis() - st;if (time > tw) {System.out.println(score + "\t" + time + "ms");if (time > tl) {tle++;}} else {System.out.println(score);}total += score;if (score > best) {best = score;bidx = z;}if (score < worst) {worst = score;widx = z;}} catch (Exception e) {System.out.println(z + ":\t" + e.getMessage());re++;}}System.out.println("total: " + total);System.out.println("best: " + bidx + ": " + best);System.out.println("worst: " + widx + ": " + worst);System.out.println("RE: " + re);System.out.println("TLE: " + tle);} else {long score = solve(caseNum);System.out.println(score);}} else {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));init(br);solve(br);br.close();}}static long solve(int z) throws Exception {StringBuilder sb = new StringBuilder();sb.append(z);while (sb.length() < 3) {sb.insert(0, '0');}File file = new File("G:\\yuki\\009\\in\\in" + sb.toString() + ".txt");BufferedReader br = new BufferedReader(new FileReader(file));init(br);long res = solve(br);br.close();// test();// long res = 0;return res;}static void init(BufferedReader br) throws Exception {endTime = System.currentTimeMillis() + limitTime;N = Integer.parseInt(br.readLine());a = new long[N];b = new long[N];for (int i = 0; i < N; i++) {String[] sa = br.readLine().split(" ");a[i] = Long.parseLong(sa[0]);b[i] = Long.parseLong(sa[1]);}order = new ArrayList<>(N);for (int i = 0; i < N; i++) {order.add(i);}}static long solve(BufferedReader br) throws Exception {List<PriorityQueue<State>> list = new ArrayList<>(51);for (int i = 0; i <= T; i++) {list.add(new PriorityQueue<>());}State fst = new State();fst.a = Arrays.copyOf(a, N);fst.b = Arrays.copyOf(b, N);fst.dm = Math.max(Math.abs(a[0] - g), Math.abs(b[0] - g));fst.u = new ArrayList<>(0);fst.v = new ArrayList<>(0);list.get(0).add(fst);for (int i = 0; i < T; i++) {PriorityQueue<State> que = list.get(i);State st = que.peek();State res = solve1(st);if (res == null) {break;}list.get(i + 1).add(res);}while (System.currentTimeMillis() < endTime) {for (int t = 0; t < T; t++) {PriorityQueue<State> que = list.get(t);if (que.isEmpty()) {break;}List<State> target = new ArrayList<>(queCap);for (int i = 0; i < queCap; i++) {if (que.isEmpty()) {break;}target.add(que.poll());}que.clear();que.addAll(target);PriorityQueue<State> que2 = list.get(t + 1);for (State st : target) {List<State> resList = solve2(st);que2.addAll(resList);}}PriorityQueue<State> que = list.get(T);if (que.size() > 1) {State st = que.poll();que.clear();que.add(st);}}State ans = fst;for (int i = T; i >= 0; i--) {PriorityQueue<State> que = list.get(i);if (!que.isEmpty()) {State st = que.peek();if (st.dm < ans.dm) {ans = st;}}}if (!batch) {output(ans);}if (readFile && !batch) {System.out.println(ans.dm);System.out.println(ans.dm2);}long sub = (long) Math.ceil(100000 * Math.log10(ans.dm + 1));long score = 2000000 - sub;return score;}static State solve1(State st) {State ret = clone(st);int ui = 0;Collections.shuffle(order);for (int vi : order) {if (vi == ui) {continue;}long aa = (ret.a[ui] + ret.a[vi]) / 2;long ab = (ret.b[ui] + ret.b[vi]) / 2;long da = Math.abs(aa - g);long db = Math.abs(ab - g);long dm = Math.max(da, db);if (dm < ret.dm) {ret.a[ui] = aa;ret.a[vi] = aa;ret.b[ui] = ab;ret.b[vi] = ab;ret.dm = dm;ret.dm2 = g;for (int i = 1; i < N; i++) {long aa2 = (ret.a[0] + ret.a[i]) / 2;long ab2 = (ret.b[0] + ret.b[i]) / 2;long da2 = Math.abs(aa2 - g);long db2 = Math.abs(ab2 - g);long dm2 = Math.max(da2, db2);if (dm2 < ret.dm2) {ret.dm2 = dm2;}}ret.t++;ret.u.add(ui);ret.v.add(vi);return ret;}}return null;}static List<State> solve2(State st) {Collections.shuffle(order);List<State> retList = new ArrayList<>(nextNum);label:while (retList.size() < nextNum) {State ret = clone(st);int ui = rand(N);for (int vi : order) {if (vi == ui) {continue;}long aa = (ret.a[ui] + ret.a[vi]) / 2;long ab = (ret.b[ui] + ret.b[vi]) / 2;if (ui == 0 || vi == 0) {long da = Math.abs(aa - g);long db = Math.abs(ab - g);long dm = Math.max(da, db);if (dm < ret.dm) {ret.a[ui] = aa;ret.a[vi] = aa;ret.b[ui] = ab;ret.b[vi] = ab;ret.dm = dm;ret.dm2 = g;for (int i = 1; i < N; i++) {long aa2 = (ret.a[0] + ret.a[i]) / 2;long ab2 = (ret.b[0] + ret.b[i]) / 2;long da2 = Math.abs(aa2 - g);long db2 = Math.abs(ab2 - g);long dm2 = Math.max(da2, db2);if (dm2 < ret.dm2) {ret.dm2 = dm2;}}ret.t++;ret.u.add(ui);ret.v.add(vi);retList.add(ret);continue label;}} else {long aa2 = (ret.a[0] + aa) / 2;long ab2 = (ret.b[0] + ab) / 2;long da2 = Math.abs(aa2 - g);long db2 = Math.abs(ab2 - g);long dm2 = Math.max(da2, db2);if (dm2 < ret.dm2) {ret.a[ui] = aa;ret.a[vi] = aa;ret.b[ui] = ab;ret.b[vi] = ab;ret.dm2 = dm2;ret.t++;ret.u.add(ui);ret.v.add(vi);retList.add(ret);continue label;}}}break;}return retList;}static void output(State ans) {PrintWriter pw = new PrintWriter(System.out);pw.println(ans.t);for (int i = 0; i < ans.t; i++) {StringBuilder sb = new StringBuilder();sb.append(ans.u.get(i) + 1);sb.append(' ');sb.append(ans.v.get(i) + 1);pw.println(sb.toString());}pw.flush();}static int rand(int r) {return (int) (Math.random() * r);}static void test() throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int x = Integer.parseInt(br.readLine());for (int i = 0; i < x; i++) {String[] sa = br.readLine().split(" ");int u = Integer.parseInt(sa[0]) - 1;int v = Integer.parseInt(sa[1]) - 1;long aa = (a[u] + a[v]) / 2;long ab = (b[u] + b[v]) / 2;a[u] = aa;a[v] = aa;b[u] = ab;b[v] = ab;}long da = Math.abs(a[0] - g);long db = Math.abs(b[0] - g);long dm = Math.max(da, db);System.out.println(dm);}static class State implements Comparable<State> {long[] a, b;long dm, dm2;int t;List<Integer> u, v;@Overridepublic int compareTo(State o) {if (dm != o.dm) {return Long.compare(dm, o.dm);}return Long.compare(dm2, o.dm2);}}static State clone(State st) {State ret = new State();ret.a = Arrays.copyOf(st.a, N);ret.b = Arrays.copyOf(st.b, N);ret.dm = st.dm;ret.dm2 = st.dm2;ret.t = st.t;ret.u = new ArrayList<>(st.t + 1);ret.u.addAll(st.u);ret.v = new ArrayList<>(st.t + 1);ret.v.addAll(st.v);return ret;}}