Submission #19079


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,1000){
    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 0
Code Size 1926 Byte
Status TLE
Exec Time 10032 ms
Memory 928 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 69
TLE × 2
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 TLE 10030 ms 804 KB
00_mini_02.txt TLE 10032 ms 808 KB
00_sample_01.txt AC 901 ms 772 KB
00_sample_02.txt AC 9452 ms 808 KB
00_sample_03.txt AC 1467 ms 768 KB
01_rnd_11_01.txt AC 8255 ms 808 KB
01_rnd_11_02.txt AC 8294 ms 812 KB
01_rnd_11_03.txt AC 8263 ms 808 KB
01_rnd_11_04.txt AC 8248 ms 780 KB
01_rnd_11_05.txt AC 8247 ms 848 KB
01_rnd_11_06.txt AC 8216 ms 808 KB
01_rnd_11_07.txt AC 8195 ms 916 KB
01_rnd_11_08.txt AC 8157 ms 808 KB
01_rnd_11_09.txt AC 8177 ms 812 KB
01_rnd_11_10.txt AC 8139 ms 784 KB
01_rnd_11_11.txt AC 8127 ms 776 KB
01_rnd_11_12.txt AC 7163 ms 816 KB
01_rnd_11_13.txt AC 696 ms 736 KB
01_rnd_11_14.txt AC 1618 ms 780 KB
01_rnd_11_15.txt AC 7885 ms 808 KB
01_rnd_11_16.txt AC 4915 ms 812 KB
01_rnd_11_17.txt AC 3340 ms 776 KB
01_rnd_11_18.txt AC 5619 ms 808 KB
01_rnd_11_19.txt AC 7458 ms 808 KB
01_rnd_11_20.txt AC 7424 ms 808 KB
01_rnd_11_21.txt AC 4817 ms 812 KB
01_rnd_11_22.txt AC 2974 ms 784 KB
01_rnd_7_01.txt AC 8717 ms 920 KB
01_rnd_7_02.txt AC 8744 ms 808 KB
01_rnd_7_03.txt AC 8976 ms 804 KB
01_rnd_7_04.txt AC 8797 ms 800 KB
01_rnd_7_05.txt AC 8772 ms 800 KB
01_rnd_7_06.txt AC 8772 ms 864 KB
01_rnd_7_07.txt AC 8728 ms 772 KB
01_rnd_7_08.txt AC 8677 ms 800 KB
01_rnd_7_09.txt AC 8647 ms 804 KB
01_rnd_7_10.txt AC 8653 ms 812 KB
01_rnd_7_11.txt AC 8597 ms 924 KB
01_rnd_7_12.txt AC 5066 ms 784 KB
01_rnd_7_13.txt AC 8330 ms 812 KB
01_rnd_7_14.txt AC 5530 ms 808 KB
01_rnd_7_15.txt AC 4718 ms 840 KB
01_rnd_7_16.txt AC 7945 ms 804 KB
01_rnd_7_17.txt AC 4651 ms 896 KB
01_rnd_7_18.txt AC 5074 ms 780 KB
01_rnd_7_19.txt AC 2212 ms 784 KB
01_rnd_7_20.txt AC 2993 ms 788 KB
01_rnd_7_21.txt AC 4991 ms 816 KB
01_rnd_7_22.txt AC 1729 ms 812 KB
01_rnd_8_01.txt AC 8476 ms 776 KB
01_rnd_8_02.txt AC 8491 ms 812 KB
01_rnd_8_03.txt AC 8496 ms 812 KB
01_rnd_8_04.txt AC 8536 ms 928 KB
01_rnd_8_05.txt AC 8505 ms 916 KB
01_rnd_8_06.txt AC 8495 ms 912 KB
01_rnd_8_07.txt AC 8514 ms 856 KB
01_rnd_8_08.txt AC 8489 ms 808 KB
01_rnd_8_09.txt AC 8444 ms 776 KB
01_rnd_8_10.txt AC 8440 ms 812 KB
01_rnd_8_11.txt AC 8416 ms 920 KB
01_rnd_8_12.txt AC 5740 ms 904 KB
01_rnd_8_13.txt AC 870 ms 784 KB
01_rnd_8_14.txt AC 5773 ms 780 KB
01_rnd_8_15.txt AC 4240 ms 812 KB
01_rnd_8_16.txt AC 3881 ms 808 KB
01_rnd_8_17.txt AC 8877 ms 808 KB
01_rnd_8_18.txt AC 1810 ms 784 KB
01_rnd_8_19.txt AC 4169 ms 808 KB
01_rnd_8_20.txt AC 5728 ms 880 KB
01_rnd_8_21.txt AC 1745 ms 780 KB
01_rnd_8_22.txt AC 7623 ms 784 KB