999ms

Untitled

Oct 23rd, 2021
491
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) begin(x), end(x)
  4.  
  5. using namespace std;
  6. using ll = long long;
  7.  
  8. bool psp(string &s) {
  9.   int b = 0;
  10.   for (char ch: s) {
  11.     if (ch == '(') {
  12.       b++;
  13.     } else if (ch == ')') {
  14.       b--;
  15.     }
  16.     if (b < 0) return false;
  17.   }
  18.   return b == 0;
  19. }
  20.  
  21. const string signs = "+-*";
  22.  
  23. // +-*
  24. vector<string> bad = {
  25.   "++",
  26.   "+*",
  27.   "-+",
  28.   "-*",
  29.   "*+",
  30.   "**"
  31. };
  32.  
  33. bool is_correct(string &s) {
  34.   const int n = (int) s.size();
  35.   for (int i = 1; i < n - 1; i++) {
  36.     if (!isdigit(s[i - 1]) && isdigit(s[i]) && isdigit(s[i + 1])) {
  37.       if (s[i] == '0') {
  38.         return false; // leading zeros
  39.       }
  40.     }
  41.   }
  42.  
  43.   for (int i = 0; i < n; i++) {
  44.     if (s[i] == '(') {
  45.       if (i > 0) {
  46.         if (isdigit(s[i - 1])) return false;
  47.       }
  48.     }
  49.     if (s[i] == ')') {
  50.       if (i + 1 < n) {
  51.         if (isdigit(s[i + 1])) return false;
  52.       }
  53.     }
  54.   }
  55.  
  56.   if (s[0] == '+') {
  57.     return false;
  58.   }
  59.  
  60.   if (s[0] == '*') {
  61.     return false;
  62.   }
  63.  
  64.   if (s.size() > 1) {
  65.     if (s[0] == '0' && isdigit(s[1])) {
  66.       return false;
  67.     }
  68.   }
  69.  
  70.  
  71.   for (int i = 0; i < n - 1; i++) {
  72.     string f = s.substr(i, 2);
  73.     if (find(all(bad), f) != bad.end()) {
  74.       return false;
  75.     }
  76.   }
  77.  
  78.   return true;
  79. }
  80.  
  81. const int KEK = -1e9 - 12341;
  82.  
  83. enum OP {
  84.   MUL,
  85.   SUM,
  86.   MIN,
  87.   VAL
  88. };
  89.  
  90. string compress(string t) {
  91.   string x;
  92.   int n = (int) t.size();
  93.   for (int i = 0; i < n;) {
  94.     if (t[i] != '-') {
  95.       x.push_back(t[i]);
  96.       i++;
  97.     } else {
  98.       int j = i;
  99.       int c = 0;
  100.       while (j < n && t[j] == '-') {
  101.         c ^= 1;
  102.         j++;
  103.       }
  104.       if (c) {
  105.         x.push_back('-');
  106.       } else {
  107.         x.push_back('-');
  108.         x.push_back('-');
  109.       }
  110.       i = j;
  111.     }
  112.   }
  113.   return x;
  114. }
  115.  
  116. int get2(string s) { // 01+-*
  117.   if (s.empty() || s[0] == '*' || s[0] == '+') {
  118.     return KEK;
  119.   }
  120.  
  121.   int n = (int) s.size();
  122.  
  123.   // minus is unary operation
  124.   // --1010 -> reverse with +
  125.   // +-1010 -> reverse with -
  126.   // *-1234 -> use like unary
  127.  
  128.   int ptr = 0;
  129.   for (int i = 0; i < n; i++) {
  130.     if (i > 0 && s[ptr - 1] == '-' && s[i] == '-') {
  131.       s[ptr - 1] = '+';
  132.     } else if (i > 0 && s[ptr - 1] == '+' && s[i] == '-') {
  133.       s[ptr - 1] = '-';
  134.     } else {
  135.       s[ptr++] = s[i];
  136.     }
  137.   }
  138.   s.resize(ptr);
  139.   n = ptr;
  140.  
  141.   vector<pair<int, int>> arr;
  142.   for (int i = 0; i < n;) {
  143.     if (s[i] == '+') {
  144.       arr.emplace_back(SUM, 0);
  145.       i++;
  146.     } else if (s[i] == '-') {
  147.       arr.emplace_back(MIN, 0);
  148.       i++;
  149.     } else if (s[i] == '*') {
  150.       arr.emplace_back(MUL, 0);
  151.       i++;
  152.     } else {
  153.       int val = 0;
  154.       while (i < n && isdigit(s[i])) {
  155.         val *= 2;
  156.         val += s[i] - '0';
  157.         i++;
  158.       }
  159.       arr.emplace_back(VAL, val);
  160.     }
  161.   }
  162.  
  163.   int k = (int) arr.size();
  164.   ptr = 0;
  165.   for (int i = 0; i < k; i++) {
  166.     if (arr[i].first == MIN) {
  167.       if (i + 1 == k) return KEK;
  168.       if (arr[i + 1].first != VAL) return KEK;
  169.       arr[i + 1].second *= -1;
  170.       if (i > 0 && arr[ptr - 1].first != MUL) {
  171.         arr[ptr++] = {SUM, 0};
  172.       }
  173.     } else {
  174.       arr[ptr++] = arr[i];
  175.     }
  176.   }
  177.  
  178.   // +*10
  179.  
  180.   arr.resize(ptr);
  181.   k = ptr;
  182.  
  183.   ptr = 0;
  184.   for (int i = 0; i < k;) {
  185.     if (arr[i].first == MUL) {
  186.       if (i + 1 >= k || arr[i + 1].first != VAL) return KEK;
  187.       arr[ptr - 1].second *= arr[i + 1].second;
  188.       i += 2;
  189.     } else {
  190.       arr[ptr++] = arr[i++];
  191.     }
  192.   }
  193.   k = ptr;
  194.   arr.resize(k);
  195.  
  196.   // 0101 +
  197.   int answer = 0;
  198.   for (auto[fl, val]: arr) {
  199.     if (fl == VAL) {
  200.       answer += val;
  201.     }
  202.   }
  203.   if (arr.back().first != VAL) {
  204.     return KEK;
  205.   }
  206.   return answer;
  207.  
  208. }
  209.  
  210. string to_bin(int val) {
  211.   string res;
  212.   if (val == 0) return "0";
  213.   while (val) {
  214.     res.push_back(char('0' + (val & 1)));
  215.     val >>= 1;
  216.   }
  217.  
  218.   reverse(all(res));
  219.   return res;
  220. }
  221.  
  222. int get(string s) {
  223.   s = "(" + s + ")";
  224.   int n = (int) s.size();
  225.   vector<pair<int, int>> psp;
  226.   vector<int> ind;
  227.   for (int i = 0; i < n; i++) {
  228.     if (s[i] == '(') {
  229.       ind.push_back(i);
  230.     }
  231.     if (s[i] == ')') {
  232.       psp.emplace_back(ind.back(), i);
  233.       ind.pop_back();
  234.     }
  235.   }
  236.   sort(all(psp));
  237.   reverse(all(psp));
  238.   for (auto[l, r]: psp) {
  239.     if (l + 1 == r) { // ()
  240.       return KEK;
  241.     }
  242.     string cur = s.substr(l + 1, r - l - 1);
  243.  
  244.     int value = get2(cur);
  245.     if (value == KEK) return KEK;
  246.  
  247.     for (int i = l; i <= r; i++) {
  248.       s[i] = '0';
  249.     }
  250.     if (l == 0) {
  251.       return value;
  252.     }
  253.     if (value < 0) {
  254.       s[l] = '-';
  255.     }
  256.     string b = to_bin(abs(value));
  257.     int le = (int) b.size();
  258.     for (int j = 0; j < le; j++) {
  259.       s[r - j] = b[le - 1 - j];
  260.     }
  261.   }
  262.  
  263.   return KEK;
  264. }
  265.  
  266. bool check(const string &s) {
  267.   // 01+-*()=
  268.   if (count(all(s), '=') != 1) return false;
  269.  
  270.   int mid = (int) s.find('=');
  271.  
  272.   string left = s.substr(0, mid);
  273.   string right = s.substr(mid + 1, s.size() - mid - 1);
  274.  
  275.   if (left.empty() || right.empty()) return false;
  276.   if (!psp(left) || !psp(right)) return false;
  277.  
  278.   if (!is_correct(left) || !is_correct(right)) return false;
  279.  
  280.   left = compress(left);
  281.   right = compress(right);
  282.  
  283.   int leftRes = get(left);
  284.   int rightRes = get(right);
  285.   if (leftRes == KEK || rightRes == KEK) return false;
  286.   return leftRes == rightRes;
  287. }
  288.  
  289. void solve() {
  290.   string s;
  291.   cin >> s;
  292.   // [01+-*()=]*
  293.   // [A-Za-z]*
  294.   vector<char> arr;
  295.   const int n = (int) s.size();
  296.   for (int i = 0; i < n; i++) {
  297.     if (s[i] >= 'a' && s[i] <= 'z' || s[i] >= 'A' && s[i] <= 'Z') {
  298.       arr.push_back(s[i]);
  299.     }
  300.   }
  301.   sort(all(arr));
  302.   arr.erase(unique(all(arr)), end(arr));
  303.  
  304.   if (arr.size() > 8) {
  305.     cout << 0 << '\n';
  306.     return;
  307.   }
  308.  
  309.   string c = "01+-*()=";
  310.   sort(all(c));
  311.   vector<char> rep(256);
  312.   iota(all(rep), 0);
  313.   vector<string> correct;
  314.   long long answer = 0;
  315.   set<string> used;
  316.   do {
  317.     for (int i = 0; i < int(arr.size()); i++) {
  318.       rep[arr[i]] = c[i];
  319.     }
  320.  
  321.     string t = s;
  322.     for (char &i: t) {
  323.       i = rep[i];
  324.     }
  325.     if (used.count(t)) continue;
  326.     used.insert(t);
  327.  
  328.     if (check(t)) {
  329.       answer++;
  330.     }
  331.   } while (next_permutation(all(c)));
  332.  
  333.   cout << answer << '\n';
  334. }
  335.  
  336. int main() {
  337.   ios_base::sync_with_stdio(false);
  338.   cin.tie(nullptr);
  339.   solve();
  340. }
  341.  
RAW Paste Data