# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
130724 | 2019-07-16T04:14:37 Z | semiauto | CEOI16_icc (CEOI16_icc) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; int i,j,k,sa,sb,l,r,m,x; int parent[101],mas[101],a[101],b[101]; bool fix[101]; void run(int n) { for (i=1;i<=n;i++) parent[i]=i; for (j=1;j<n;j++) { for (i=1;i<=n;i++) fix[i]=0; for (i=1;i<=n;i++) fix[parent[i]]=1; k=0; for (i=1;i<=n;i++) if (fix[i]) mas[++k]=i; while (true) { for (i=1;i<=n;i++) fix[i]=0; for (i=1;i<=(k/2);) if (!fix[mas[(rand()%k)+1]]) { fix[mas[(rand()%k)+1]]=1; i++; } sa=sb=0; for (i=1;i<=n;i++) { if (fix[parent[i]]) a[++sa]=i; else b[++sb]=i; } if (query(sa,sb,a,b)) break; } l=1;r=sa; while (l!=r) { m=(l+r)/2; for (i=1;i<=n;i++) mas[i]=0; for (i=l;i<=m;i++) mas[i-l+1]=a[i]; if (query(m-l+1,b,mas,sb)) r=m; else l=m+1; } x=l; l=1;r=sb; while (l!=r) { m=(l+r)/2; for (i=1;i<=n;i++) mas[i]=0; for (i=l;i<=m;i++) mas[i-l+1]=b[i]; if (query(sa,m-l+1,a,mas)) r=m; else l=m+1; } setRoad(a[x],b[l]); } return; }