Submission #8817548

---

Source Code Expand

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.SplittableRandom;

public final class Main {
	private static final long startTime = System.currentTimeMillis();
	private static final boolean DEBUG = false;
	private static final long TL = 1000;
	private static final Scanner sc = new Scanner(System.in);
	private static final SplittableRandom rnd = new SplittableRandom(42);
	private static final int N = 1000;
	private static final int S = 1000;
	private static final int K = 20;
	private int[] x = new int[N], y = new int[N], c = new int[N];
	private boolean[][] used = new boolean[N][N], gEn = new boolean[N][N];
	private int[][] usedCount = new int[N][N], unusedCount = new int[N][N], g = new int[N][];
	private int[][] trees = new int[S][K - 1];

	public static void main(String[] args) {
		new Main().solve();
	}

	void solve() {
		sc.nextLine();
		for (int i = 0; i < N; i++) {
			x[i] = Integer.parseInt(sc.next());
			y[i] = Integer.parseInt(sc.next());
			c[i] = Integer.parseInt(sc.next());
		}
		for (int i = 0; i < S; i++) {
			for (int j = 0; j < K - 1; j++) {
				trees[i][j] = Integer.parseInt(sc.next()) - 1;
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < i; j++) {
				gEn[i][j] = gEn[j][i] = sq(x[i] - x[j]) + sq(y[i] - y[j]) <= sq(c[i] + c[j]);
			}
		}
		for (int i = 0; i < N; i++) {
			int count = 0;
			for (int j = 0; j < N; j++) {
				if (gEn[i][j]) ++count;
			}
			int[] row = new int[count];
			for (int j = 0, p = 0; j < N; j++) {
				if (gEn[i][j]) {
					row[p++] = j;
				}
			}
			g[i] = row;
		}
		long worstTime = 0;
		long beforeTime = System.currentTimeMillis();
		Solution bestSol = null;
		for (int turn = 0; ; turn++) {
			if (beforeTime + worstTime - startTime > TL) {
				debug("turn:%d", turn);
				break;
			}
			Solution sol = findSolution();
			debug("score:%d", sol.score);
			if (bestSol == null || sol.score > bestSol.score) {
				bestSol = sol;
			}
			long curTime = System.currentTimeMillis();
			worstTime = Math.max(worstTime, curTime - beforeTime);
			beforeTime = curTime;
		}
		PrintWriter writer = new PrintWriter(System.out);
		writer.println(bestSol.a.size);
		for (int i = 0; i < bestSol.a.size; i++) {
			writer.println((bestSol.a.a[i] + 1) + " " + (bestSol.b.a[i] + 1));
		}
		for (int i = 0; i < S; i++) {
			for (int j = 0; j < K - 1; j++) {
				writer.print((bestSol.v[i][j] + 1) + " ");
			}
			writer.println(bestSol.v[i][K - 1] + 1);
		}
		writer.flush();
		System.err.println("score:" + bestSol.score);
	}

	Solution findSolution() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				used[i][j] = false;
				usedCount[i][j] = 0;
				unusedCount[i][j] = 0;
			}
		}
		int[] vs = new int[N];
		for (int i = 0; i < N; i++) {
			vs[i] = -((c[i] << 10) | i); // use g[i].len than c[i]?
		}
		Arrays.sort(vs);
		for (int i = 0; i < N; i++) {
			vs[i] = (-vs[i]) & 0x3FF;
		}
		Solution sol = new Solution();
		int[] tis = new int[S];
		for (int i = 0; i < S; i++) {
			tis[i] = i;
		}
		IntAry after = new IntAry();
		for (int i = 0; i < S; i++) {
			int pos = rnd.nextInt(S - i) + i;
			swap(tis, i, pos);
			int[] mapping = findTree(tis[i], vs);
			if (mapping == null) {
				after.add(tis[i]);
			} else {
				sol.score += 100;
				addUsed(tis[i], mapping, sol);
			}
		}
		for (int i = 0; i < after.size; i++) {
			for (int j = 0; j < K; j++) {
				sol.v[after.a[i]][j] = j;
			}
		}
		sol.a = new IntAry();
		sol.b = new IntAry();
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (used[i][j]) {
					sol.a.add(i);
					sol.b.add(j);
				}
			}
		}
//		sol.validate();
		return sol;
	}

	boolean[] usedInSearch = new boolean[N];

	int[] findTree(int ti, int[] vs) {
		for (int i = 0; i < 10; i++) {
			int[] ret = findTree(ti, vs[rnd.nextInt() & 127]);
			if (ret != null) {
				return ret;
			}
		}
		return null;
	}

	int[] findTree(int ti, int center) {
		int[] ret = new int[K];
		int[] tree = trees[ti];
		ret[0] = center;
		usedInSearch[center] = true;
		int depth = 1;
		int stopCount = 0;
		LOOP:
		for (int i = 0; i < 100000; i++) {
			if (depth == K) {
				Arrays.fill(usedInSearch, false);
				return ret;
			}
			if (stopCount == 100) {
				// backtrack
				if (depth == 1) break;
				for (int j = 1; j < depth; j++) {
					usedInSearch[ret[j]] = false;
				}
				depth = 1;
				continue;
			}
			int p = ret[tree[depth - 1]];
			int cur = g[p][rnd.nextInt(g[p].length)];
			if (usedInSearch[cur] || unusedCount[p][cur] > 0) {
				stopCount++;
				continue;
			}
			for (int j = 0; j < depth; j++) {
				if (j == tree[depth - 1]) continue;
				if (used[cur][ret[j]]) {
					stopCount++;
					continue LOOP;
				}
			}
			stopCount = 0;
			ret[depth] = cur;
			usedInSearch[cur] = true;
			depth++;
		}
		for (int j = 0; j < depth; j++) {
			usedInSearch[ret[j]] = false;
		}
		return null;
	}

	void addUsed(int ti, int[] mapping, Solution sol) {
		int[] tree = trees[ti];
		sol.v[ti][0] = mapping[0];
		for (int j = 1; j < K; j++) {
			sol.v[ti][j] = mapping[j];
			int t = mapping[j];
			int f = mapping[tree[j - 1]];
			assert (gEn[f][t]);
			used[f][t] = used[t][f] = true;
			usedCount[f][t]++;
			usedCount[t][f]++;
			for (int k = 0; k < j; k++) {
				if (k == tree[j - 1]) continue;
				int nf = mapping[k];
				assert (!used[t][nf]);
				unusedCount[nf][t]++;
				unusedCount[t][nf]++;
			}
		}
	}

	class Solution {
		IntAry a, b;
		int[][] v = new int[S][K];
		int score;

		void validate() {
			int score = 0;
			for (int i = 0; i < S; i++) {
				int otherEdge = 0;
				boolean ok = true;
				for (int j = 1; j < K; j++) {
					for (int k = 0; k < j; k++) {
						int t = v[i][j];
						int f = v[i][k];
						if (k == trees[i][j - 1]) {
							if (!used[f][t]) {
								ok = false;
							}
						} else {
							if (used[f][t]) {
								otherEdge++;
							}
						}
					}
				}
				if (!ok) {
					System.err.println("invalid");
				} else if (otherEdge == 0) {
					score += 100;
					System.err.println(100);
				} else if (otherEdge == 1) {
					score += 10;
					System.err.println(10);
				} else if (otherEdge == 2) {
					score += 1;
					System.err.println(1);
				} else {
					System.err.println(0);
				}
			}
			System.err.println("score:" + score);
		}
	}

	private static int sq(int v) {
		return v * v;
	}

	static final class IntAry {
		int[] a;
		int size;

		IntAry() {
			a = new int[16];
		}

		IntAry(int cap) {
			a = new int[cap];
		}

		IntAry(int[] a) {
			this.a = a;
			this.size = a.length;
		}

		IntAry(IntAry that) {
			a = that.a.clone();
			size = that.size;
		}

		@Override
		public String toString() {
			return Arrays.toString(Arrays.copyOf(a, size));
		}

		IntAry copyOf(int from, int to) {
			return new IntAry(Arrays.copyOfRange(this.a, from, to));
		}

		void add(int v) {
			if (size == a.length) {
				int[] na = new int[a.length * 2];
				System.arraycopy(a, 0, na, 0, size);
				a = na;
			}
			a[size++] = v;
		}

		void addAll(IntAry ia) {
			if (this.size + ia.size < a.length) {
				int[] na = new int[this.size + ia.size];
				System.arraycopy(a, 0, na, 0, size);
				a = na;
			}
			System.arraycopy(ia.a, 0, a, size, ia.size);
			size += ia.size;
		}

		void clear() {
			size = 0;
		}

		int pop() {
			size--;
			return a[size];
		}

		int back() {
			return a[size - 1];
		}

		void remove(int pos) {
			System.arraycopy(a, pos + 1, a, pos, size - pos - 1);
			size--;
		}

		void swapRemove(int pos) {
			swap(a, pos, size - 1);
			size--;
		}

		void sort() {
			Arrays.sort(a, 0, size);
		}
	}

	static void swap(int[] a, int p1, int p2) {
		int tmp = a[p1];
		a[p1] = a[p2];
		a[p2] = tmp;
	}

	static void debug(String fmt, Object... obj) {
		if (DEBUG) System.err.printf(fmt + "\n", obj);
	}
}

Submission Info

Judge Result