I sort the the 2^k states by the bits it contains, then check the states in order, and always TLE #22

Then, I choose a state randomly in the 2^k states and check if it's legal, and get accepted……

part of my code:

 63     int ans = (1 << k) - 1;
 64     int tot = 1 << k;
 65     int times = 0;
 66     while (tot > 0 && (times * realm < (500000000))) {
 67         int now = rand() % tot;
 68         if (countBit(arr[now]) < countBit(ans)){
 69             memset(visit,0,sizeof(visit));
 70             times++;
 71             if (dfs(0,arr[now])) {
 72                 ans = arr[now];
 73             }
 74         }
 75         arr[now] = arr[--tot];
 76     }

If you use G++, it's better to use standart function (__builtin_popcount(n)) instead of countBit(n)