//ライブラリへのリンク //https://drive.google.com/drive/folders/1QDp2j94gwNBUf6lF2M-FTs9NVAKFpw5R #include using namespace std; using pii=pair; using tii=tuple; using qii=tuple; using ll=long long; using ull=unsigned long long; using ld=long double; constexpr int INF=1e9; constexpr ll INF_ll=1e18; #define rep(i,n) for (int i=0;i<(int)(n);i++) #define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++) #define all(v) v.begin(),v.end() #define len(v) ((int)v.size()) template inline bool chmin(T &a,T b){ if(a>b){ a=b; return true; } return false; } template inline bool chmax(T &a,T b){ if(a inline bool chmin_ref(T &a,const T &b){ if(a>b){ a=b; return true; } return false; } template inline bool chmax_ref(T &a,const T &b){ if(a(now-start).count(); return ms; } int get_ms_all_program(){ auto now=chrono::steady_clock::now(); int ms=chrono::duration_cast(now-program_start).count(); return ms; } } mt19937 mt; uint32_t rand_int(uint32_t r){ //[0,r) assert(r!=0); return ((uint64_t)mt()*r)>>32; } int rand_int(int l,int r){ //[l,r) assert(l T get_random_element(const vector &v){ assert(!v.empty()); return v[rand_int(len(v))]; } template void add(vector &a,vector b){ for(auto i:b) a.push_back(i); } constexpr int N=50,K=100; array D; array,N*N> G; int one(int i,int j){ return i*N+j; } pii two(int x){ return {x/N,x%N}; } namespace Solver{ double calc_e(const array &is_cut){ array is_tree; is_tree.fill(false); rep(i,N*N){ if(is_cut[i]) continue; if((int)rand_int(10) root; root.fill(-1); rep(i,N*N){ if(!is_tree[i]) continue; if(root[i]!=-1) continue; queue q; q.push(i); root[i]=i; while(!q.empty()){ int x=q.front(); q.pop(); for(auto y:G[x]){ if(!is_tree[y]) continue; if(root[y]!=-1) continue; root[y]=i; q.push(y); } } } array cnt; cnt.fill(0); rep(i,N*N){ if(root[i]!=-1) cnt[root[i]]++; } double ret=0; rep(i,N*N){ ret+=cnt[i]*cnt[i]; } ret/=N*N; return ret; } double e0=0; double calc_score(const array &is_cut,int try_turn){ assert(try_turn!=0); double e=0; rep(_,try_turn) e+=calc_e(is_cut); e/=try_turn; return 1e6*(1+log(e0/e)); } void solve(){ array is_cut,best_is_cut; is_cut.fill(false); best_is_cut.fill(false); rep(_,1000) e0+=calc_e(is_cut); e0/=1000; /*double best_score=0; rep(i,N*N){ auto new_is_cut=is_cut; new_is_cut[i]=true; double new_score=calc_score(new_is_cut,100); cerr << i << " " << new_score << " " << best_score << endl; if(best_score ans; rep(i,N*N){ if(D[i]==0) continue; if(best_is_cut[i]) ans.push_back(i); } assert(len(ans)> n >> k; rep(i,N){ rep(j,N){ char c; cin >> c; D[one(i,j)]=c-'0'; } } rep(i,N*N) G[i].fill(-1); rep(i,N){ rep(j,N){ if(j+1