Submission #19206


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,200){
    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 D - シャッフル席替え
User EmK
Language C++ (G++ 4.6.4)
Score 100
Code Size 1925 Byte
Status AC
Exec Time 3549 ms
Memory 836 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 3538 ms 784 KB
00_mini_02.txt AC 3549 ms 796 KB
00_sample_01.txt AC 219 ms 784 KB
00_sample_02.txt AC 2003 ms 816 KB
00_sample_03.txt AC 316 ms 784 KB
01_rnd_11_01.txt AC 1711 ms 740 KB
01_rnd_11_02.txt AC 1716 ms 788 KB
01_rnd_11_03.txt AC 1777 ms 776 KB
01_rnd_11_04.txt AC 1719 ms 792 KB
01_rnd_11_05.txt AC 1716 ms 764 KB
01_rnd_11_06.txt AC 1715 ms 784 KB
01_rnd_11_07.txt AC 1710 ms 796 KB
01_rnd_11_08.txt AC 1711 ms 756 KB
01_rnd_11_09.txt AC 1706 ms 792 KB
01_rnd_11_10.txt AC 1710 ms 784 KB
01_rnd_11_11.txt AC 1707 ms 792 KB
01_rnd_11_12.txt AC 1485 ms 792 KB
01_rnd_11_13.txt AC 154 ms 772 KB
01_rnd_11_14.txt AC 341 ms 756 KB
01_rnd_11_15.txt AC 1700 ms 792 KB
01_rnd_11_16.txt AC 1035 ms 784 KB
01_rnd_11_17.txt AC 642 ms 772 KB
01_rnd_11_18.txt AC 1180 ms 788 KB
01_rnd_11_19.txt AC 1557 ms 792 KB
01_rnd_11_20.txt AC 1559 ms 792 KB
01_rnd_11_21.txt AC 1020 ms 836 KB
01_rnd_11_22.txt AC 638 ms 788 KB
01_rnd_7_01.txt AC 1819 ms 788 KB
01_rnd_7_02.txt AC 1833 ms 788 KB
01_rnd_7_03.txt AC 1851 ms 820 KB
01_rnd_7_04.txt AC 1844 ms 796 KB
01_rnd_7_05.txt AC 1844 ms 760 KB
01_rnd_7_06.txt AC 1845 ms 788 KB
01_rnd_7_07.txt AC 1839 ms 796 KB
01_rnd_7_08.txt AC 1830 ms 780 KB
01_rnd_7_09.txt AC 1825 ms 776 KB
01_rnd_7_10.txt AC 1832 ms 804 KB
01_rnd_7_11.txt AC 1808 ms 788 KB
01_rnd_7_12.txt AC 1098 ms 788 KB
01_rnd_7_13.txt AC 1751 ms 752 KB
01_rnd_7_14.txt AC 1168 ms 788 KB
01_rnd_7_15.txt AC 1000 ms 784 KB
01_rnd_7_16.txt AC 1677 ms 784 KB
01_rnd_7_17.txt AC 769 ms 760 KB
01_rnd_7_18.txt AC 1077 ms 780 KB
01_rnd_7_19.txt AC 480 ms 772 KB
01_rnd_7_20.txt AC 638 ms 764 KB
01_rnd_7_21.txt AC 1056 ms 792 KB
01_rnd_7_22.txt AC 378 ms 792 KB
01_rnd_8_01.txt AC 1774 ms 784 KB
01_rnd_8_02.txt AC 1784 ms 772 KB
01_rnd_8_03.txt AC 1792 ms 788 KB
01_rnd_8_04.txt AC 1794 ms 788 KB
01_rnd_8_05.txt AC 1801 ms 792 KB
01_rnd_8_06.txt AC 1867 ms 784 KB
01_rnd_8_07.txt AC 1795 ms 772 KB
01_rnd_8_08.txt AC 1794 ms 788 KB
01_rnd_8_09.txt AC 1786 ms 780 KB
01_rnd_8_10.txt AC 1782 ms 796 KB
01_rnd_8_11.txt AC 1783 ms 764 KB
01_rnd_8_12.txt AC 1198 ms 772 KB
01_rnd_8_13.txt AC 191 ms 780 KB
01_rnd_8_14.txt AC 1266 ms 836 KB
01_rnd_8_15.txt AC 895 ms 736 KB
01_rnd_8_16.txt AC 730 ms 784 KB
01_rnd_8_17.txt AC 1633 ms 780 KB
01_rnd_8_18.txt AC 399 ms 788 KB
01_rnd_8_19.txt AC 890 ms 784 KB
01_rnd_8_20.txt AC 1212 ms 792 KB
01_rnd_8_21.txt AC 389 ms 784 KB
01_rnd_8_22.txt AC 1611 ms 780 KB