結果

問題 No.5020 Averaging
ユーザー ks2mks2m
提出日時 2024-02-25 15:21:56
言語 Java21
(openjdk 21)
結果
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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 869 ms
71,184 KB
testcase_01 AC 868 ms
73,668 KB
testcase_02 AC 858 ms
71,152 KB
testcase_03 AC 862 ms
73,520 KB
testcase_04 AC 866 ms
71,028 KB
testcase_05 AC 868 ms
72,880 KB
testcase_06 AC 854 ms
72,612 KB
testcase_07 AC 877 ms
73,876 KB
testcase_08 AC 871 ms
72,852 KB
testcase_09 AC 857 ms
70,572 KB
testcase_10 AC 854 ms
72,888 KB
testcase_11 AC 870 ms
73,568 KB
testcase_12 AC 865 ms
72,876 KB
testcase_13 AC 869 ms
72,928 KB
testcase_14 AC 865 ms
73,032 KB
testcase_15 AC 858 ms
71,284 KB
testcase_16 AC 871 ms
73,492 KB
testcase_17 AC 869 ms
72,800 KB
testcase_18 AC 869 ms
72,976 KB
testcase_19 AC 870 ms
71,032 KB
testcase_20 AC 859 ms
72,884 KB
testcase_21 AC 870 ms
74,092 KB
testcase_22 AC 866 ms
72,904 KB
testcase_23 AC 856 ms
72,864 KB
testcase_24 AC 874 ms
70,788 KB
testcase_25 AC 875 ms
73,976 KB
testcase_26 AC 868 ms
72,808 KB
testcase_27 AC 866 ms
73,572 KB
testcase_28 AC 868 ms
73,120 KB
testcase_29 AC 866 ms
73,228 KB
testcase_30 AC 866 ms
70,500 KB
testcase_31 AC 865 ms
72,896 KB
testcase_32 AC 872 ms
71,900 KB
testcase_33 AC 870 ms
73,092 KB
testcase_34 AC 876 ms
71,048 KB
testcase_35 AC 869 ms
72,848 KB
testcase_36 AC 873 ms
71,080 KB
testcase_37 AC 872 ms
73,092 KB
testcase_38 AC 868 ms
70,952 KB
testcase_39 AC 871 ms
72,748 KB
testcase_40 AC 866 ms
73,844 KB
testcase_41 AC 866 ms
73,116 KB
testcase_42 AC 864 ms
71,400 KB
testcase_43 AC 867 ms
71,996 KB
testcase_44 AC 872 ms
72,896 KB
testcase_45 AC 869 ms
73,100 KB
testcase_46 AC 866 ms
72,768 KB
testcase_47 AC 869 ms
72,676 KB
testcase_48 AC 856 ms
72,708 KB
testcase_49 AC 874 ms
72,236 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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; // TODO
				long 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;

		@Override
		public 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;
	}
}
0