Submission #19203


Source Code Expand

Copy
// compile with "g++ XXX.cc -mno-cygwin -O2" in Cygwin

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<functional>
#include<complex>
#include<bitset>
#include<cassert>

using namespace std;
#define BET(a,b,c) ((a)<=(b)&&(b)<(c))
#define FOR(i,n) for(int i=0,i##_end=(int(n));i<i##_end;i++)
#define FOR3(i,a,b) for(int i=a,i##_end=b;i<i##_end;i++)
#define FOR_EACH(it,v) for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++)
#define SZ(x) (int)(x.size())
#define ALL(x) (x).begin(),(x).end()
#define MP make_pair
#define CLS(x,val) memset((x) , val , sizeof(x)) 
typedef long long ll_t;
typedef long double ld_t;
typedef vector<int> VI; 
typedef vector<VI> VVI;
typedef complex<int> xy_t;

template<typename T> void debug(T v , string delimiter = "\n")
{ for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++) cout << *it << delimiter; cout << flush ;}

int dx[]  = {0,1,0,-1};
int dy[]  = {1,0,-1,0};
string ds = "SENW";

const double PI = 4.0*atan(1.0);

int A[111],B[111];
int perm[100];
bool ng[111][111];
int main() {
  int N,M,K;
  cin>>N>>M>>K;
  memset(ng , 0 , sizeof(ng));
  FOR(i,M) {
    cin>>A[i]>>B[i];
    ng[A[i]][B[i]]=true;
    ng[B[i]][A[i]]=true;
  }
  double all = 0 , p = 0;
  FOR(P,10000) FOR(Q,150){
    FOR(i,N) perm[i] = i;
    FOR(_,K){
      int p1 = rand() % N;
      int p2 = rand() % N;
      if(p1==p2) { _--; continue; }
      swap(perm[p1] , perm[p2]);
    }
    bool dame = false;
    FOR(i,N){
      int ii = (i+1)%N;
      if(ng[perm[i]][perm[ii]]) {
        dame = true; break;
      }
    }
    if(!dame){
      p++;
    }
    all++;
  }
  printf("%.10f\n" , p / all);
  return 0 ;
}

Submission Info

Submission Time
Task A - GPA計算
User EmK
Language C++ (G++ 4.6.4)
Score 0
Code Size 1925 Byte
Status WA
Exec Time 991 ms
Memory 816 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 2
WA × 30
Set Name Test Cases
all 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 02_rndmax_01.txt, 02_rndmax_02.txt, 02_rndmax_03.txt, 02_rndmax_04.txt, 02_rndmax_05.txt, 02_rndmax_06.txt, 02_rndmax_07.txt, 02_rndmax_08.txt, 02_rndmax_09.txt, 02_rndmax_10.txt, 03_mini_01.txt, 03_mini_02.txt, 03_mini_03.txt, 03_mini_04.txt, 03_mini_05.txt, 04_samemax_01.txt, 04_samemax_02.txt, 04_samemax_03.txt, 04_samemax_04.txt, 04_samemax_05.txt
Case Name Status Exec Time Memory
00_sample_01.txt WA 329 ms 780 KB
00_sample_02.txt WA 69 ms 788 KB
01_rnd_01.txt WA 140 ms 784 KB
01_rnd_02.txt WA 121 ms 812 KB
01_rnd_03.txt WA 237 ms 792 KB
01_rnd_04.txt WA 660 ms 764 KB
01_rnd_05.txt WA 394 ms 792 KB
01_rnd_06.txt WA 870 ms 784 KB
01_rnd_07.txt WA 300 ms 784 KB
01_rnd_08.txt WA 873 ms 792 KB
01_rnd_09.txt WA 186 ms 788 KB
01_rnd_10.txt WA 346 ms 792 KB
02_rndmax_01.txt WA 980 ms 784 KB
02_rndmax_02.txt WA 980 ms 788 KB
02_rndmax_03.txt WA 982 ms 768 KB
02_rndmax_04.txt WA 980 ms 788 KB
02_rndmax_05.txt WA 981 ms 796 KB
02_rndmax_06.txt WA 981 ms 796 KB
02_rndmax_07.txt WA 980 ms 788 KB
02_rndmax_08.txt WA 991 ms 804 KB
02_rndmax_09.txt WA 984 ms 788 KB
02_rndmax_10.txt WA 985 ms 788 KB
03_mini_01.txt WA 36 ms 816 KB
03_mini_02.txt WA 36 ms 788 KB
03_mini_03.txt WA 37 ms 792 KB
03_mini_04.txt AC 35 ms 792 KB
03_mini_05.txt WA 40 ms 732 KB
04_samemax_01.txt WA 981 ms 768 KB
04_samemax_02.txt WA 983 ms 796 KB
04_samemax_03.txt WA 980 ms 788 KB
04_samemax_04.txt AC 981 ms 780 KB
04_samemax_05.txt WA 983 ms 784 KB