Submission #19529


Source Code Expand

Copy
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		String[] nmk = s.readLine().split(" ");
		int N = Integer.valueOf(nmk[0]);
		int M = Integer.valueOf(nmk[1]);
		int K = Integer.valueOf(nmk[2]);
		boolean[][] forbidden = new boolean[N][N];
		for (int i = 0 ; i < M ; i++) {
			String[] data = s.readLine().split(" ");
			int a = Integer.valueOf(data[0]);
			int b = Integer.valueOf(data[1]);
			forbidden[a][b] = true;
			forbidden[b][a] = true;
		}

		long till = System.currentTimeMillis() + 9000;
		long succeeded = 0;
		long tried = 0;
		
		int[] init = new int[N];
		for (int i = 0 ; i < N ; i++) {
			init[i] = i;
		}
		while (true) {
			int[] now = init.clone();
			if (tried % 100 == 0) {
				if (System.currentTimeMillis() >= till) {
					break;
				}
			}
			for (int k = 0 ; k < K ; k++) {
				int a = (int)(Math.random() * N);
				int b = (int)(Math.random() * N);
				if (a == b) {
					k--;
					continue;
				}
				int t = now[a];
				now[a] = now[b];
				now[b] = t;
			}
			
			tried++;
			if (!forbidden[now[0]][now[N-1]]) {
				boolean isok = true;
				for (int i = 0 ; i < N - 1 ; i++) {
					if (forbidden[now[i]][now[i+1]]) {
						isok = false;
						break;
					}
				}
				if (isok) {
					succeeded++;
				}
			}
		}
		System.out.println(1.0d * succeeded / tried);
	}
}

Submission Info

Submission Time
Task D - シャッフル席替え
User hamadu
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 1639 Byte
Status AC
Exec Time 9567 ms
Memory 30176 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 9426 ms 28748 KB
00_mini_02.txt AC 9425 ms 29072 KB
00_sample_01.txt AC 9423 ms 29324 KB
00_sample_02.txt AC 9418 ms 28772 KB
00_sample_03.txt AC 9425 ms 30112 KB
01_rnd_11_01.txt AC 9429 ms 29136 KB
01_rnd_11_02.txt AC 9439 ms 29112 KB
01_rnd_11_03.txt AC 9418 ms 29100 KB
01_rnd_11_04.txt AC 9422 ms 29112 KB
01_rnd_11_05.txt AC 9446 ms 29184 KB
01_rnd_11_06.txt AC 9421 ms 29172 KB
01_rnd_11_07.txt AC 9421 ms 29096 KB
01_rnd_11_08.txt AC 9454 ms 29424 KB
01_rnd_11_09.txt AC 9424 ms 29028 KB
01_rnd_11_10.txt AC 9419 ms 29020 KB
01_rnd_11_11.txt AC 9427 ms 29072 KB
01_rnd_11_12.txt AC 9486 ms 29092 KB
01_rnd_11_13.txt AC 9424 ms 28824 KB
01_rnd_11_14.txt AC 9427 ms 29948 KB
01_rnd_11_15.txt AC 9429 ms 29108 KB
01_rnd_11_16.txt AC 9422 ms 29232 KB
01_rnd_11_17.txt AC 9451 ms 29196 KB
01_rnd_11_18.txt AC 9420 ms 29116 KB
01_rnd_11_19.txt AC 9433 ms 29112 KB
01_rnd_11_20.txt AC 9441 ms 29092 KB
01_rnd_11_21.txt AC 9433 ms 29184 KB
01_rnd_11_22.txt AC 9432 ms 29192 KB
01_rnd_7_01.txt AC 9456 ms 29472 KB
01_rnd_7_02.txt AC 9460 ms 29060 KB
01_rnd_7_03.txt AC 9431 ms 29072 KB
01_rnd_7_04.txt AC 9458 ms 29072 KB
01_rnd_7_05.txt AC 9427 ms 29176 KB
01_rnd_7_06.txt AC 9567 ms 29060 KB
01_rnd_7_07.txt AC 9515 ms 28756 KB
01_rnd_7_08.txt AC 9428 ms 28828 KB
01_rnd_7_09.txt AC 9505 ms 28648 KB
01_rnd_7_10.txt AC 9425 ms 28772 KB
01_rnd_7_11.txt AC 9423 ms 28736 KB
01_rnd_7_12.txt AC 9567 ms 28940 KB
01_rnd_7_13.txt AC 9466 ms 29200 KB
01_rnd_7_14.txt AC 9461 ms 29184 KB
01_rnd_7_15.txt AC 9416 ms 29048 KB
01_rnd_7_16.txt AC 9417 ms 29048 KB
01_rnd_7_17.txt AC 9421 ms 29276 KB
01_rnd_7_18.txt AC 9427 ms 28784 KB
01_rnd_7_19.txt AC 9428 ms 28796 KB
01_rnd_7_20.txt AC 9415 ms 28636 KB
01_rnd_7_21.txt AC 9448 ms 28632 KB
01_rnd_7_22.txt AC 9433 ms 29184 KB
01_rnd_8_01.txt AC 9426 ms 29044 KB
01_rnd_8_02.txt AC 9421 ms 29088 KB
01_rnd_8_03.txt AC 9423 ms 29548 KB
01_rnd_8_04.txt AC 9421 ms 29052 KB
01_rnd_8_05.txt AC 9423 ms 29112 KB
01_rnd_8_06.txt AC 9453 ms 29188 KB
01_rnd_8_07.txt AC 9458 ms 29084 KB
01_rnd_8_08.txt AC 9427 ms 29060 KB
01_rnd_8_09.txt AC 9420 ms 28660 KB
01_rnd_8_10.txt AC 9436 ms 28704 KB
01_rnd_8_11.txt AC 9440 ms 28736 KB
01_rnd_8_12.txt AC 9444 ms 29100 KB
01_rnd_8_13.txt AC 9450 ms 30176 KB
01_rnd_8_14.txt AC 9465 ms 29052 KB
01_rnd_8_15.txt AC 9427 ms 29180 KB
01_rnd_8_16.txt AC 9435 ms 29796 KB
01_rnd_8_17.txt AC 9414 ms 29104 KB
01_rnd_8_18.txt AC 9423 ms 29108 KB
01_rnd_8_19.txt AC 9419 ms 29048 KB
01_rnd_8_20.txt AC 9430 ms 29096 KB
01_rnd_8_21.txt AC 9421 ms 28832 KB
01_rnd_8_22.txt AC 9438 ms 28728 KB