1
class Solution {
2
 public:
3
  int superpalindromesInRange(string left, string right) {
4
    int ans = 9 >= stol(left) && 9 <= stol(right) ? 1 : 0;
5
    for (int dig = 1; dig < 10; dig++) {
6
      bool isOdd = dig % 2 && dig != 1;
7
      int innerLen = (dig >> 1) - 1, innerLim = max(1, (int)pow(2, innerLen)), midPos = dig >> 1,
8
          midLim = isOdd ? 3 : 1;
9
      for (int edge = 1; edge < 3; edge++) {
10
        string pal(dig, '0');
11
        pal[0] = (char)(edge + 48);
12
        pal[dig - 1] = (char)(edge + 48);
13
        if (edge == 2) innerLim = 1, midLim = min(midLim, 2);
14
        for (int inner = 0; inner < innerLim; inner++) {
15
          if (inner > 0) {
16
            string innerStr = bitset<3>(inner).to_string();
17
            innerStr = innerStr.substr(3 - innerLen);
18
            for (int i = 0; i < innerLen; i++) {
19
              pal[1 + i] = innerStr[i];
20
              pal[dig - 2 - i] = innerStr[i];
21
            }
22
          }
23
          for (int mid = 0; mid < midLim; mid++) {
24
            if (isOdd) pal[midPos] = (char)(mid + 48);
25
            long square = stol(pal) * stol(pal);
26
            if (square > stol(right)) return ans;
27
            if (square >= stol(left) && isPal(to_string(square))) ans++;
28
          }
29
        }
30
      }
31
    }
32
    return ans;
33
  }
34

35
  bool isPal(string str) {
36
    for (int i = 0, j = str.length() - 1; i < j; i++, j--)
37
      if (str[i] != str[j]) return false;
38
    return true;
39
  }
40
};