Submission #2616436


Source Code Expand

Copy
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.NoSuchElementException;

public class Main {
	private static void solve() {
		int n = nei();
		int m = nei();
		int k = nei();
		int[][] abs = nis2(m, 2);
		boolean[][] ng = new boolean[n][n];
		for (int i = 0; i < m; i++) {
			int p = abs[i][0];
			int q = abs[i][1];
			ng[p][q] = true;
			ng[q][p] = true;
		}
		int[] hito = new int[n];
		long st = System.currentTimeMillis();
		long totalCount = 0;
		long okCount = 0;
		while (totalCount % 100 != 0 || System.currentTimeMillis() - st < 8000) {
			for (int i = 0; i < n; i++) {
				hito[i] = i;
			}
			for (int i = 0; i < k; i++) {
				int x = (int) (Math.random() * n);
				int y = (int) (Math.random() * (n - 1)) + 1;
				if (x == y)
					y = 0;
				int tmp = hito[x];
				hito[x] = hito[y];
				hito[y] = tmp;
			}
			boolean isOk = true;
			for (int i = 0; i < n; i++) {
				if (ng[hito[i]][hito[(i + 1) % n]]) {
					isOk = false;
					break;
				}
			}
			totalCount++;
			if (isOk)
				okCount++;
		}
		out((double) okCount / totalCount);
	}

	// returns (x, y, d) s.t. ax + by = d
	static long[] exgcd(long a, long b) {
		int sa = a < 0 ? -1 : 1;
		int sb = b < 0 ? -1 : 1;
		a *= sa;
		b *= sb;
		long x = 1;
		long y = 0;
		long z = 0;
		long w = 1;
		while (b > 0) {
			long q = a / b;
			long t = z;
			z = x - q * z;
			x = t;
			t = w;
			w = y - q * w;
			y = t;
			t = b;
			b = a - q * b;
			a = t;
		}
		return new long[] { x * sa, y * sb, a };
	}

	static int[] lis(int[] s) {
		int n = s.length;
		int[] dp = new int[n];
		int[] ids = new int[n];
		int[] pids = new int[n];
		dp[0] = s[0];
		int len = 1;
		int lidx = 0;
		for (int i = 1; i < n; i++) {
			int idx = bs(s[i], dp, 0, len);
			dp[idx] = s[i];
			ids[idx] = i;
			if (idx == len) {
				lidx = i;
				len++;
			}
			if (idx > 0)
				pids[i] = ids[idx - 1];
		}
		int[] lis = new int[len];
		lis[len - 1] = s[lidx];
		for (int i = len - 1; i >= 0; i--) {
			lis[i] = s[lidx];
			lidx = pids[lidx];
		}
		return lis;
	}

	static int bs(int a, int[] as, int from, int num) {
		int min = from;
		int max = from + num - 1;
		while (min < max) {
			int mid = min + max >> 1;
			if (as[mid] < a)
				min = mid + 1;
			else if (as[mid] > a)
				max = mid;
			else
				return mid;
		}
		return as[min] < a ? min + 1 : min;
	}

	static int gcd(int x, int y) {
		x = (x ^ x >> 31) - (x >> 31);
		y = (y ^ y >> 31) - (y >> 31);
		if (x < y) {
			x ^= y;
			y ^= x;
			x ^= y;
		}
		int z = x % y;
		if (z == 0)
			return y;
		return gcd(y, z);
	}

	static long gcd(long x, long y) {
		x = (x ^ x >> 63) - (x >> 63);
		y = (y ^ y >> 63) - (y >> 63);
		if (x < y) {
			x ^= y;
			y ^= x;
			x ^= y;
		}
		long z = x % y;
		if (z == 0)
			return y;
		return gcd(y, z);
	}

	static long modinv(long a, long mod) {
		return BigInteger.valueOf(a).modInverse(BigInteger.valueOf(mod)).longValueExact();
	}

	static int lcm(int x, int y) {
		x = (x ^ x >> 31) - (x >> 31);
		y = (y ^ y >> 31) - (y >> 31);
		return x / gcd(x, y) * y;
	}

	static long lcm(long x, long y) {
		x = (x ^ x >> 63) - (x >> 63);
		y = (y ^ y >> 63) - (y >> 63);
		return x / gcd(x, y) * y;
	}

	static int abs(int x) {
		return x < 0 ? -x : x;
	}

	static long abs(long x) {
		return x < 0 ? -x : x;
	}

	static int min(int a, int b) {
		return a < b ? a : b;
	}

	static long min(long a, long b) {
		return a < b ? a : b;
	}

	static int max(int a, int b) {
		return a > b ? a : b;
	}

	static long max(long a, long b) {
		return a > b ? a : b;
	}

	static int clamp(int a, int min, int max) {
		return a < min ? min : a > max ? max : a;
	}

	static long clamp(long a, long min, long max) {
		return a < min ? min : a > max ? max : a;
	}

	static void out(String val) {
		IO.out(val);
	}

	static void out(Object val) {
		IO.out(String.valueOf(val));
	}

	static void out(int val) {
		IO.out(String.valueOf(val));
	}

	static void out(long val) {
		IO.out(String.valueOf(val));
	}

	static void out(char val) {
		IO.out(String.valueOf(val));
	}

	static void out(float val) {
		IO.out(String.valueOf(val));
	}

	static void out(double val) {
		IO.out(String.valueOf(val));
	}

	static void out(boolean val) {
		IO.out(String.valueOf(val));
	}

	static void kil(String val) {
		IO.out(val);
		IO.flush();
		System.exit(0);
	}

	static void kil(Object val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(int val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(long val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(char val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(float val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(double val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(boolean val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static String nes() {
		return IO.next();
	}

	static int nei() {
		return IO.nextInt();
	}

	static long nel() {
		return IO.nextLong();
	}

	static double ned() {
		return IO.nextDouble();
	}

	static char nec() {
		return IO.nextChar();
	}

	static String[] nss(int n) {
		String[] as = new String[n];
		for (int i = 0; i < n; i++) {
			as[i] = IO.next();
		}
		return as;
	}

	static int[] nis(int n) {
		int[] as = new int[n];
		for (int i = 0; i < n; i++) {
			as[i] = IO.nextInt();
		}
		return as;
	}

	static long[] nls(int n) {
		long[] as = new long[n];
		for (int i = 0; i < n; i++) {
			as[i] = IO.nextLong();
		}
		return as;
	}

	static double[] nds(int n) {
		double[] as = new double[n];
		for (int i = 0; i < n; i++) {
			as[i] = IO.nextDouble();
		}
		return as;
	}

	static char[] ncs(int n) {
		char[] as = new char[n];
		for (int i = 0; i < n; i++) {
			as[i] = IO.nextChar();
		}
		return as;
	}

	static String[][] nss2(int n, int m) {
		String[][] as = new String[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				as[i][j] = IO.next();
			}
		}
		return as;
	}

	static int[][] nis2(int n, int m) {
		int[][] as = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				as[i][j] = IO.nextInt();
			}
		}
		return as;
	}

	static long[][] nls2(int n, int m) {
		long[][] as = new long[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				as[i][j] = IO.nextLong();
			}
		}
		return as;
	}

	static double[][] nds2(int n, int m) {
		double[][] as = new double[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				as[i][j] = IO.nextDouble();
			}
		}
		return as;
	}

	static char[][] ncs2(int n, int m) {
		char[][] as = new char[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				as[i][j] = IO.nextChar();
			}
		}
		return as;
	}

	static int parseInt(String val) {
		return Integer.parseInt(val);
	}

	static int parseInt(char val) {
		return Integer.parseInt(String.valueOf(val));
	}

	static long parseLong(String val) {
		return Long.parseLong(val);
	}

	public static void main(String[] args) {
		try {
			solve();
			IO.flush();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

final class IO {
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out, false);
	private static final byte[] buffer = new byte[1024];
	private static int ptr = 0;
	private static int len = 0;

	private static boolean hasNextByte() {
		if (ptr < len)
			return true;
		ptr = 0;
		try {
			len = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		return len > 0;
	}

	private static int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	static boolean hasNext() {
		byte c;
		while (hasNextByte() && ((c = buffer[ptr]) < '!' || c > '~'))
			ptr++;
		return hasNextByte();
	}

	static String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (b >= '!' && b <= '~') {
			sb.append((char) b);
			b = readByte();
		}
		return sb.toString();
	}

	static char nextChar() {
		if (!hasNext())
			throw new NoSuchElementException();
		return (char) readByte();
	}

	static long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		int sign = 1;
		int b = readByte();
		if (b == '-') {
			sign = -1;
			b = readByte();
		}
		if (b < '0' || '9' < b)
			throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9')
				n = n * 10 + b - '0';
			else if (b == -1 || b < '!' || b > '~')
				return n * sign;
			else
				throw new NumberFormatException();
			b = readByte();
		}
	}

	static int nextInt() {
		if (!hasNext())
			throw new NoSuchElementException();
		int n = 0;
		int sign = 1;
		int b = readByte();
		if (b == '-') {
			sign = -1;
			b = readByte();
		}
		if (b < '0' || '9' < b)
			throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9')
				n = n * 10 + b - '0';
			else if (b == -1 || b < '!' || b > '~')
				return n * sign;
			else
				throw new NumberFormatException();
			b = readByte();
		}
	}

	static double nextDouble() {
		return Double.parseDouble(next());
	}

	static void out(String val) {
		out.println(val);
	}

	static void flush() {
		out.flush();
	}
}

Submission Info

Submission Time
Task D - シャッフル席替え
User saharan
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 9948 Byte
Status AC
Exec Time 8074 ms
Memory 25920 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 71
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_rnd_11_01.txt, 01_rnd_11_02.txt, 01_rnd_11_03.txt, 01_rnd_11_04.txt, 01_rnd_11_05.txt, 01_rnd_11_06.txt, 01_rnd_11_07.txt, 01_rnd_11_08.txt, 01_rnd_11_09.txt, 01_rnd_11_10.txt, 01_rnd_11_11.txt, 01_rnd_11_12.txt, 01_rnd_11_13.txt, 01_rnd_11_14.txt, 01_rnd_11_15.txt, 01_rnd_11_16.txt, 01_rnd_11_17.txt, 01_rnd_11_18.txt, 01_rnd_11_19.txt, 01_rnd_11_20.txt, 01_rnd_11_21.txt, 01_rnd_11_22.txt, 01_rnd_7_01.txt, 01_rnd_7_02.txt, 01_rnd_7_03.txt, 01_rnd_7_04.txt, 01_rnd_7_05.txt, 01_rnd_7_06.txt, 01_rnd_7_07.txt, 01_rnd_7_08.txt, 01_rnd_7_09.txt, 01_rnd_7_10.txt, 01_rnd_7_11.txt, 01_rnd_7_12.txt, 01_rnd_7_13.txt, 01_rnd_7_14.txt, 01_rnd_7_15.txt, 01_rnd_7_16.txt, 01_rnd_7_17.txt, 01_rnd_7_18.txt, 01_rnd_7_19.txt, 01_rnd_7_20.txt, 01_rnd_7_21.txt, 01_rnd_7_22.txt, 01_rnd_8_01.txt, 01_rnd_8_02.txt, 01_rnd_8_03.txt, 01_rnd_8_04.txt, 01_rnd_8_05.txt, 01_rnd_8_06.txt, 01_rnd_8_07.txt, 01_rnd_8_08.txt, 01_rnd_8_09.txt, 01_rnd_8_10.txt, 01_rnd_8_11.txt, 01_rnd_8_12.txt, 01_rnd_8_13.txt, 01_rnd_8_14.txt, 01_rnd_8_15.txt, 01_rnd_8_16.txt, 01_rnd_8_17.txt, 01_rnd_8_18.txt, 01_rnd_8_19.txt, 01_rnd_8_20.txt, 01_rnd_8_21.txt, 01_rnd_8_22.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 8068 ms 18388 KB
00_mini_02.txt AC 8070 ms 20172 KB
00_sample_01.txt AC 8068 ms 19312 KB
00_sample_02.txt AC 8071 ms 19924 KB
00_sample_03.txt AC 8071 ms 19900 KB
01_rnd_11_01.txt AC 8071 ms 20712 KB
01_rnd_11_02.txt AC 8071 ms 20728 KB
01_rnd_11_03.txt AC 8070 ms 19188 KB
01_rnd_11_04.txt AC 8070 ms 22592 KB
01_rnd_11_05.txt AC 8070 ms 19636 KB
01_rnd_11_06.txt AC 8070 ms 22328 KB
01_rnd_11_07.txt AC 8070 ms 22576 KB
01_rnd_11_08.txt AC 8072 ms 21308 KB
01_rnd_11_09.txt AC 8070 ms 22836 KB
01_rnd_11_10.txt AC 8070 ms 22452 KB
01_rnd_11_11.txt AC 8072 ms 22204 KB
01_rnd_11_12.txt AC 8071 ms 20844 KB
01_rnd_11_13.txt AC 8071 ms 22424 KB
01_rnd_11_14.txt AC 8070 ms 20076 KB
01_rnd_11_15.txt AC 8070 ms 19648 KB
01_rnd_11_16.txt AC 8070 ms 21076 KB
01_rnd_11_17.txt AC 8072 ms 21824 KB
01_rnd_11_18.txt AC 8071 ms 22080 KB
01_rnd_11_19.txt AC 8073 ms 19864 KB
01_rnd_11_20.txt AC 8072 ms 17204 KB
01_rnd_11_21.txt AC 8071 ms 20876 KB
01_rnd_11_22.txt AC 8072 ms 21124 KB
01_rnd_7_01.txt AC 8071 ms 20136 KB
01_rnd_7_02.txt AC 8070 ms 22800 KB
01_rnd_7_03.txt AC 8072 ms 22204 KB
01_rnd_7_04.txt AC 8071 ms 22996 KB
01_rnd_7_05.txt AC 8071 ms 20396 KB
01_rnd_7_06.txt AC 8072 ms 20016 KB
01_rnd_7_07.txt AC 8070 ms 20532 KB
01_rnd_7_08.txt AC 8071 ms 22356 KB
01_rnd_7_09.txt AC 8072 ms 20052 KB
01_rnd_7_10.txt AC 8069 ms 22784 KB
01_rnd_7_11.txt AC 8070 ms 19924 KB
01_rnd_7_12.txt AC 8068 ms 19900 KB
01_rnd_7_13.txt AC 8072 ms 25920 KB
01_rnd_7_14.txt AC 8071 ms 19892 KB
01_rnd_7_15.txt AC 8073 ms 22776 KB
01_rnd_7_16.txt AC 8073 ms 20148 KB
01_rnd_7_17.txt AC 8071 ms 20856 KB
01_rnd_7_18.txt AC 8071 ms 19328 KB
01_rnd_7_19.txt AC 8070 ms 19796 KB
01_rnd_7_20.txt AC 8069 ms 20204 KB
01_rnd_7_21.txt AC 8071 ms 22228 KB
01_rnd_7_22.txt AC 8071 ms 22228 KB
01_rnd_8_01.txt AC 8070 ms 22572 KB
01_rnd_8_02.txt AC 8074 ms 18116 KB
01_rnd_8_03.txt AC 8073 ms 20288 KB
01_rnd_8_04.txt AC 8071 ms 22672 KB
01_rnd_8_05.txt AC 8070 ms 21180 KB
01_rnd_8_06.txt AC 8072 ms 23124 KB
01_rnd_8_07.txt AC 8072 ms 21812 KB
01_rnd_8_08.txt AC 8071 ms 20368 KB
01_rnd_8_09.txt AC 8071 ms 19632 KB
01_rnd_8_10.txt AC 8071 ms 22228 KB
01_rnd_8_11.txt AC 8071 ms 17364 KB
01_rnd_8_12.txt AC 8072 ms 22068 KB
01_rnd_8_13.txt AC 8070 ms 22792 KB
01_rnd_8_14.txt AC 8072 ms 19768 KB
01_rnd_8_15.txt AC 8071 ms 20740 KB
01_rnd_8_16.txt AC 8071 ms 20224 KB
01_rnd_8_17.txt AC 8071 ms 19844 KB
01_rnd_8_18.txt AC 8073 ms 20624 KB
01_rnd_8_19.txt AC 8074 ms 22272 KB
01_rnd_8_20.txt AC 8071 ms 20396 KB
01_rnd_8_21.txt AC 8071 ms 18644 KB
01_rnd_8_22.txt AC 8071 ms 23124 KB