結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 14:49:46 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 88 ms / 1,000 ms |
コード長 | 3,840 bytes |
コンパイル時間 | 2,180 ms |
実行使用メモリ | 37,408 KB |
スコア | 4,521,707 |
最終ジャッジ日時 | 2022-07-30 14:49:53 |
合計ジャッジ時間 | 6,528 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
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.HashSet;import java.util.List;import java.util.Set;public class Main {static boolean batch = false;static boolean readFile = false;static int num = 0;static int a = 5;static int N, M;static Obj[] pln;public static void main(String[] args) throws Exception {if (batch) {readFile = true;}if (readFile) {if (batch) {long tl = 1000;long tw = (long) (tl * 0.9);long total = 0;int bidx = 0;int best = 0;int widx = 0;int worst = 1000000000;int re = 0;int tle = 0;for (int z = 0; z < 100; z++) {try {long st = System.currentTimeMillis();int score = solve(z);long time = System.currentTimeMillis() - st;if (time > tw) {System.out.println(z + ":\t" + score + "\t" + time + "ms");if (time > tl) {tle++;}} else {System.out.println(z + ":\t" + 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 {int score = solve(num);System.out.println(score);}} else {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));init(br);solve();}}static int solve(int z) throws Exception {StringBuilder sb = new StringBuilder();sb.append(z);while (sb.length() < 4) {sb.insert(0, '0');}File file = new File("G:\\input\\" + sb.toString() + ".txt");BufferedReader br = new BufferedReader(new FileReader(file));init(br);return solve();}static void init(BufferedReader br) throws Exception {String[] sa = br.readLine().split(" ");N = Integer.parseInt(sa[0]);M = Integer.parseInt(sa[1]);pln = new Obj[N];for (int i = 0; i < N; i++) {sa = br.readLine().split(" ");Obj o = new Obj();o.t = 1;o.i = i;o.x = Integer.parseInt(sa[0]);o.y = Integer.parseInt(sa[1]);pln[i] = o;}}static int solve() throws Exception {Obj[] sta = new Obj[M];for (int i = 0; i < M; i++) {Obj o = new Obj();o.t = 2;o.i = i;sta[i] = o;}Set<Obj> rem = new HashSet<>();for (int i = 1; i < N; i++) {rem.add(pln[i]);}List<Obj> ans = new ArrayList<>();ans.add(pln[0]);Obj now = pln[0];while (!rem.isEmpty()) {int min = Integer.MAX_VALUE;Obj next = null;for (Obj o : rem) {if (next == null) {min = dist(now, o);next = o;continue;}int d = dist(now, o);if (d < min) {min = d;next = o;}}ans.add(next);rem.remove(next);now = next;}ans.add(pln[0]);PrintWriter pw = new PrintWriter(System.out);int v = ans.size();for (Obj o : sta) {pw.println(o.x + " " + o.y);}pw.println(v);pw.println("1 1");int s = 0;for (int i = 1; i < v; i++) {Obj o = ans.get(i);pw.println(o.t + " " + (o.i + 1));Obj o1 = ans.get(i - 1);int e = dist(o1, o);if (o1.t == 1) e *= a;if (o.t == 1) e *= a;s += e;}pw.flush();int score = (int) Math.round(1000000000 / (1000 + Math.sqrt(s)));return score;}static int dist(Obj o1, Obj o2) {int dx = o1.x - o2.x;int dy = o1.y - o2.y;return dx * dx + dy * dy;}static class Obj {int t, i, x, y;}}