xxZeus

recursive binflip check

Oct 24th, 2021
510
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. bool valid(int prev, int k, int after, int powerUsed) {
  2.   if (k == 0 && powerUsed == 0)
  3.     return true;
  4.   if (powerUsed == 0)
  5.     return false;
  6.   // printf("call %d %d %d %d\n", prev, k, after, powerUsed);
  7.   int toUse = pow(2, powerUsed - 1);
  8.   if (toUse > k) {
  9.     int shifted = toUse - k;
  10.     vector<bool> vals;
  11.     if (prev >= shifted) {
  12.       vals.pb(
  13.           valid(prev - shifted, shifted, after + k, powerUsed - 1));
  14.     }
  15.     if (after >= shifted) {
  16.       vals.pb(
  17.           valid(prev + k, shifted, after - shifted, powerUsed - 1));
  18.     }
  19.     for (auto x : vals)
  20.       if (x)
  21.         return true;
  22.     return false;
  23.   } else {
  24.     return valid(prev + toUse, k - toUse, after, powerUsed - 1) || valid(prev, k - toUse, after + toUse, powerUsed - 1);
  25.   }
  26. }
RAW Paste Data