# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
130947 | 2019-07-16T09:59:45 Z | semiauto | ICC (CEOI16_icc) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "icc.h" using namespace std; int i,j,k,q,sa,sb,l,r,m,x,alo,balo; int parent[101],mas[101],a[101],b[101]; int fix[101],go[101][101],r[1000000]; int n; void run(int n) { for (i=1;i<=n;i++) parent[i]=i; for (i=0;i<1000000;i++)r[i]=rand()%2; 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=0;i<k;i++) fix[parent[i]]=r[++q]; sa=sb=0; for (i=0;i<=n;i++) a[i]=b[i]=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; }if (q>500)return; l=1;r=sa; while (l!=r) { m=(l+r)/2; for (i=0;i<=n;i++) mas[i]=0; for (i=l;i<=m;i++) mas[i-l]=a[i-1]; if (query(m-l+1,sb,mas,b)) r=m; else l=m+1; } x=l; l=1;r=sb; while (l!=r) { m=(l+r)/2; for (i=0;i<=n;i++) mas[i]=0; for (i=l;i<=m;i++) mas[i-l]=b[i-1]; if (query(sa,m-l+1,a,mas)) r=m; else l=m+1; } int solo=parent[a[x-1]]; for (i=1;i<=n;i++) if (parent[i]==solo) parent[i]=parent[b[l-1]]; setRoad(b[l-1],a[x-1]); if (q>500)return; } return; }