Submission #19302


Source Code Expand

Copy
#include <iostream>
#include <iomanip>

using namespace std;

unsigned int xor128(){ 
	static unsigned int x = 123456789;
	static unsigned int y = 362436069;
	static unsigned int z = 521288629;
	static unsigned int w = 88675123; 
	unsigned int t;
	t = x ^ (x << 11);
	x = y; y = z; z = w;
	return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

bool table[16][16] = { { false } };
int arrange[16];

int main(){
	int N, M, K;
	cin >> N >> M >> K;
	for(int i = 0; i < M; ++i){
		int a, b;
		cin >> a >> b;
		table[a][b] = table[b][a] = true;
	}
	int ac = 0, tot = 0;
	for(int i = 0; i < 10000000; ++i){
		for(int j = 0; j < N; ++j){ arrange[j] = j; }
		for(int j = 0; j < K; ++j){
			int a = xor128() % N, b = xor128() % (N - 1);
			if(b >= a){ ++b; }
			swap(arrange[a], arrange[b]);
		}
		bool flag = table[arrange[0]][arrange[N - 1]];
		for(int j = 1; j < N; ++j){
			flag = flag || table[arrange[j - 1]][arrange[j]];
		}
		if(!flag){ ++ac; }
		++tot;
	}
	cout << setiosflags(ios::fixed) << setprecision(9);
	cout << static_cast<double>(ac) / tot << endl;
	return 0;
}

Submission Info

Submission Time
Task D - シャッフル席替え
User logicmachine
Language C++ (G++ 4.6.4)
Score 100
Code Size 1109 Byte
Status AC
Exec Time 4335 ms
Memory 880 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 2501 ms 780 KB
00_mini_02.txt AC 2496 ms 852 KB
00_sample_01.txt AC 402 ms 784 KB
00_sample_02.txt AC 2927 ms 732 KB
00_sample_03.txt AC 539 ms 784 KB
01_rnd_11_01.txt AC 3028 ms 780 KB
01_rnd_11_02.txt AC 3092 ms 784 KB
01_rnd_11_03.txt AC 3137 ms 772 KB
01_rnd_11_04.txt AC 3167 ms 772 KB
01_rnd_11_05.txt AC 3214 ms 844 KB
01_rnd_11_06.txt AC 3199 ms 768 KB
01_rnd_11_07.txt AC 3206 ms 784 KB
01_rnd_11_08.txt AC 3216 ms 772 KB
01_rnd_11_09.txt AC 3218 ms 860 KB
01_rnd_11_10.txt AC 3221 ms 784 KB
01_rnd_11_11.txt AC 3222 ms 724 KB
01_rnd_11_12.txt AC 2640 ms 852 KB
01_rnd_11_13.txt AC 308 ms 764 KB
01_rnd_11_14.txt AC 875 ms 776 KB
01_rnd_11_15.txt AC 3035 ms 840 KB
01_rnd_11_16.txt AC 2005 ms 776 KB
01_rnd_11_17.txt AC 1378 ms 880 KB
01_rnd_11_18.txt AC 2301 ms 776 KB
01_rnd_11_19.txt AC 4335 ms 784 KB
01_rnd_11_20.txt AC 2959 ms 784 KB
01_rnd_11_21.txt AC 2045 ms 776 KB
01_rnd_11_22.txt AC 1418 ms 784 KB
01_rnd_7_01.txt AC 2856 ms 784 KB
01_rnd_7_02.txt AC 2939 ms 780 KB
01_rnd_7_03.txt AC 2996 ms 872 KB
01_rnd_7_04.txt AC 3041 ms 800 KB
01_rnd_7_05.txt AC 3042 ms 784 KB
01_rnd_7_06.txt AC 3049 ms 880 KB
01_rnd_7_07.txt AC 3051 ms 776 KB
01_rnd_7_08.txt AC 3054 ms 772 KB
01_rnd_7_09.txt AC 3044 ms 772 KB
01_rnd_7_10.txt AC 3029 ms 784 KB
01_rnd_7_11.txt AC 3014 ms 780 KB
01_rnd_7_12.txt AC 1689 ms 872 KB
01_rnd_7_13.txt AC 2813 ms 780 KB
01_rnd_7_14.txt AC 1952 ms 852 KB
01_rnd_7_15.txt AC 1719 ms 776 KB
01_rnd_7_16.txt AC 2776 ms 776 KB
01_rnd_7_17.txt AC 1353 ms 736 KB
01_rnd_7_18.txt AC 1881 ms 864 KB
01_rnd_7_19.txt AC 963 ms 780 KB
01_rnd_7_20.txt AC 1212 ms 772 KB
01_rnd_7_21.txt AC 1858 ms 864 KB
01_rnd_7_22.txt AC 745 ms 776 KB
01_rnd_8_01.txt AC 2943 ms 776 KB
01_rnd_8_02.txt AC 2963 ms 776 KB
01_rnd_8_03.txt AC 3038 ms 736 KB
01_rnd_8_04.txt AC 3075 ms 784 KB
01_rnd_8_05.txt AC 3080 ms 780 KB
01_rnd_8_06.txt AC 3101 ms 784 KB
01_rnd_8_07.txt AC 3100 ms 780 KB
01_rnd_8_08.txt AC 3105 ms 780 KB
01_rnd_8_09.txt AC 3104 ms 776 KB
01_rnd_8_10.txt AC 3094 ms 780 KB
01_rnd_8_11.txt AC 3088 ms 864 KB
01_rnd_8_12.txt AC 1973 ms 844 KB
01_rnd_8_13.txt AC 513 ms 868 KB
01_rnd_8_14.txt AC 2108 ms 768 KB
01_rnd_8_15.txt AC 1628 ms 772 KB
01_rnd_8_16.txt AC 1377 ms 872 KB
01_rnd_8_17.txt AC 2839 ms 780 KB
01_rnd_8_18.txt AC 867 ms 724 KB
01_rnd_8_19.txt AC 1664 ms 780 KB
01_rnd_8_20.txt AC 2185 ms 784 KB
01_rnd_8_21.txt AC 869 ms 788 KB
01_rnd_8_22.txt AC 2823 ms 848 KB