Submission #19289


Source Code Expand

Copy
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>

#define REP(i,x) for(int i=0 ; i<(int)(x) ; i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

LL 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)); 
}

double randomD(){
	return (double)xor128()/(1LL<<32);
}

int main(){
	srand(215);
	int N,M,K;
	while(~scanf("%d%d%d",&N,&M,&K)){
		vector<vector<int> > bad(N,vector<int>(N,0));
		REP(i,M){
			int a,b;
			scanf("%d%d",&a,&b);
			bad[a][b] = bad[b][a] = 1;
		}
		vector<int> man(N,0);
		double ok=0,ng=0;
		REP(cnt,10000000){
			REP(i,N)man[i] = i;
			REP(k,K){
				int a = randomD()*N;
				int b = randomD()*N;
				while(a==b)b = randomD()*N;
				swap(man[a],man[b]);
			}
			int j=0;
			for(;j<N ; j++)if(bad[man[j]][man[(j+1)%N]])break;
			if(j==N)ok += 1;
			else ng += 1;
		}
		printf("%.6f\n",ok/(ok+ng));
	}
	return 0;
}

Submission Info

Submission Time
Task D - シャッフル席替え
User nel215
Language C++ (G++ 4.6.4)
Score 100
Code Size 1408 Byte
Status AC
Exec Time 7526 ms
Memory 912 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:48:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

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 7526 ms 768 KB
00_mini_02.txt AC 7486 ms 800 KB
00_sample_01.txt AC 596 ms 784 KB
00_sample_02.txt AC 4645 ms 788 KB
00_sample_03.txt AC 791 ms 780 KB
01_rnd_11_01.txt AC 4048 ms 780 KB
01_rnd_11_02.txt AC 4095 ms 904 KB
01_rnd_11_03.txt AC 4096 ms 780 KB
01_rnd_11_04.txt AC 4088 ms 796 KB
01_rnd_11_05.txt AC 4083 ms 776 KB
01_rnd_11_06.txt AC 4063 ms 796 KB
01_rnd_11_07.txt AC 4053 ms 784 KB
01_rnd_11_08.txt AC 4040 ms 776 KB
01_rnd_11_09.txt AC 4015 ms 800 KB
01_rnd_11_10.txt AC 4008 ms 784 KB
01_rnd_11_11.txt AC 3994 ms 792 KB
01_rnd_11_12.txt AC 3581 ms 800 KB
01_rnd_11_13.txt AC 695 ms 780 KB
01_rnd_11_14.txt AC 1043 ms 780 KB
01_rnd_11_15.txt AC 3927 ms 880 KB
01_rnd_11_16.txt AC 2627 ms 816 KB
01_rnd_11_17.txt AC 1670 ms 784 KB
01_rnd_11_18.txt AC 3468 ms 796 KB
01_rnd_11_19.txt AC 3714 ms 776 KB
01_rnd_11_20.txt AC 3706 ms 776 KB
01_rnd_11_21.txt AC 2559 ms 796 KB
01_rnd_11_22.txt AC 1620 ms 852 KB
01_rnd_7_01.txt AC 4223 ms 780 KB
01_rnd_7_02.txt AC 4249 ms 788 KB
01_rnd_7_03.txt AC 4272 ms 780 KB
01_rnd_7_04.txt AC 4273 ms 876 KB
01_rnd_7_05.txt AC 4274 ms 780 KB
01_rnd_7_06.txt AC 4256 ms 776 KB
01_rnd_7_07.txt AC 4208 ms 780 KB
01_rnd_7_08.txt AC 4244 ms 852 KB
01_rnd_7_09.txt AC 4185 ms 788 KB
01_rnd_7_10.txt AC 4135 ms 832 KB
01_rnd_7_11.txt AC 4146 ms 872 KB
01_rnd_7_12.txt AC 2579 ms 768 KB
01_rnd_7_13.txt AC 4053 ms 788 KB
01_rnd_7_14.txt AC 2808 ms 800 KB
01_rnd_7_15.txt AC 2442 ms 848 KB
01_rnd_7_16.txt AC 3893 ms 780 KB
01_rnd_7_17.txt AC 1765 ms 796 KB
01_rnd_7_18.txt AC 2590 ms 772 KB
01_rnd_7_19.txt AC 1684 ms 840 KB
01_rnd_7_20.txt AC 1499 ms 780 KB
01_rnd_7_21.txt AC 2504 ms 792 KB
01_rnd_7_22.txt AC 918 ms 772 KB
01_rnd_8_01.txt AC 4150 ms 864 KB
01_rnd_8_02.txt AC 4188 ms 788 KB
01_rnd_8_03.txt AC 4200 ms 844 KB
01_rnd_8_04.txt AC 4237 ms 792 KB
01_rnd_8_05.txt AC 4162 ms 912 KB
01_rnd_8_06.txt AC 4162 ms 880 KB
01_rnd_8_07.txt AC 4123 ms 788 KB
01_rnd_8_08.txt AC 4117 ms 860 KB
01_rnd_8_09.txt AC 4097 ms 904 KB
01_rnd_8_10.txt AC 4085 ms 784 KB
01_rnd_8_11.txt AC 4031 ms 780 KB
01_rnd_8_12.txt AC 2932 ms 780 KB
01_rnd_8_13.txt AC 606 ms 856 KB
01_rnd_8_14.txt AC 2981 ms 840 KB
01_rnd_8_15.txt AC 2274 ms 780 KB
01_rnd_8_16.txt AC 1783 ms 864 KB
01_rnd_8_17.txt AC 3811 ms 868 KB
01_rnd_8_18.txt AC 1005 ms 768 KB
01_rnd_8_19.txt AC 2224 ms 776 KB
01_rnd_8_20.txt AC 2875 ms 796 KB
01_rnd_8_21.txt AC 952 ms 780 KB
01_rnd_8_22.txt AC 3728 ms 828 KB