Submission #19281


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 random(){
	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 = random()*N;
				int b = random()*N;
				while(a==b)b = random()*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 0
Code Size 1404 Byte
Status CE

Compile Error

./Main.cpp: In function ‘double random()’:
./Main.cpp:37:15: error: new declaration ‘double random()’
/usr/include/stdlib.h:327:17: error: ambiguates old declaration ‘long int random()’
./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]