Advertisement
he_obviously

long?long

Apr 13th, 2020
270
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.90 KB | None | 0 0
  1. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  2. #pragma GCC optimize("unroll-loops")
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 200;
  8.  
  9. bool lesen (int left[], int right[]) {
  10.     int check[N];
  11.     for (int i = 0; i < N; ++i) {
  12.         check[i] = left[i];
  13.     }
  14.     for (int i = N - 1; i >= 0; --i) {
  15.         if (check[i] < 99) {
  16.             check[i] += 1;
  17.             break;
  18.         }
  19.         else {
  20.             check[i] = 0;
  21.         }
  22.     }
  23.     for (int i = 0; i < N; ++i) {
  24.         if (right[i] > check[i]) {
  25.             return true;
  26.         }
  27.         else if (right[i] < check[i]) {
  28.             return false;
  29.         }
  30.         else {
  31.  
  32.         }
  33.     }
  34.     return false;
  35. }
  36.  
  37. void get_mid(int left[], int right[], int mid[]) {
  38.     for (int i = 0; i < N; ++i) {
  39.         mid[i] = 0;
  40.     }
  41.     int dot = 0;
  42.     for (int i = N - 1; i >= 0; --i) {
  43.         mid[i] = (right[i] + left[i] + dot) % 100;
  44.         dot = (right[i] + left[i] + dot) / 100;
  45.     }
  46.     for (int i = 0; i < N; ++i) {
  47.         if (i != N - 1)
  48.             mid[i + 1] += 100 * (mid[i] % 2);
  49.         mid[i] = mid[i] / 2;
  50.     }
  51. }
  52.  
  53. int main()
  54. {
  55.  
  56.     string a, b;
  57.     cin >> a >> b;
  58.  
  59.     int left[N];
  60.     int right[N];
  61.     int mid[N];
  62.     int cur[2 * N];
  63.     int ans[2 * N];
  64.  
  65.     int f[2 * N];
  66.     int s[2 * N];
  67.  
  68.     for (int i = 0; i < 2 * N; ++i) {
  69.         f[i] = 0;
  70.     }
  71.  
  72.     for (int i = 0; i < 2 * N; ++i) {
  73.         s[i] = 0;
  74.     }
  75.  
  76.     if ((int)a.size() % 2 == 1) {
  77.         f[2 * N - (int)a.size() / 2 - 1] = (int) (a[0] - '0');
  78.         for (int i = (int)a.size() - 1; i >= 2; i -= 2) {
  79.             f[2 * N - (int)a.size() / 2 + i / 2 - 1] = ((int)(a[i - 1] - '0') * 10 + (int)(a[i] - '0'));
  80.         }
  81.     }
  82.     else {
  83.         for (int i = (int)a.size() - 1; i >= 1; i -= 2) {
  84.             f[2 * N - (int)a.size() / 2 + i / 2] = ((int)(a[i - 1] - '0') * 10 + (int)(a[i] - '0'));
  85.         }
  86.     }
  87.  
  88.     if ((int)b.size() % 2 == 1) {
  89.         s[2 * N - (int)b.size() / 2 - 1] = (int)(b[0] - '0');
  90.         for (int i = (int)b.size() - 1; i >= 2; i -= 2) {
  91.             s[2 * N - (int)b.size() / 2 + i / 2 - 1] = ((int)(b[i - 1] - '0') * 10 + (int)(b[i] - '0'));
  92.         }
  93.     }
  94.     else {
  95.         for (int i = (int)b.size() - 1; i >= 1; i -= 2) {
  96.             s[2 * N - (int)b.size() / 2 + i / 2] = ((int)(b[i - 1] - '0') * 10 + (int)(b[i] - '0'));
  97.         }
  98.     }
  99.  
  100.     for (int i = 0; i < 2 * N; ++i) {
  101.         if (s[i] < f[i]) {
  102.             break;
  103.         }
  104.         else if (s[i] > f[i]) {
  105.             cout << 0;
  106.             return 0;
  107.         }
  108.         else {
  109.             continue;
  110.         }
  111.     }
  112.  
  113.     int summ = 0;
  114.  
  115.     for (int i = 0; i < 2 * N; ++i) {
  116.         summ += s[i];
  117.     }
  118.  
  119.     if (summ == 1 && s[2 * N - 1] == 1) {
  120.         cout << a;
  121.         return 0;
  122.     }
  123.  
  124.     int st = 0;
  125.  
  126.     while (f[st] == 0 && st < 2 * N) {
  127.         st += 1;
  128.     }
  129.  
  130.     if (st == 2 * N) {
  131.         cout << 0;
  132.         return 0;
  133.     }
  134.  
  135.     for (int i = 0 ; i < N; ++i) {
  136.         left[i] = 0;
  137.         right[i] = f[N + i];
  138.     }
  139.  
  140.     left[N - 1] = 1;
  141.  
  142.     while (lesen(left, right)) {
  143.         for (int i = 0; i < N; ++i) {
  144.             mid[i] = 0;
  145.         }
  146.         get_mid(left, right, mid);
  147.         for (int i = 0; i < 2 * N; ++i) {
  148.             ans[i] = 0;
  149.         }
  150.         for (int i = N - 1; i >= 0; --i) {
  151.             for (int j = 0; j < 2 * N; ++j) {
  152.                 cur[j] = 0;
  153.             }
  154.             int pr = s[N + i]; int dot = 0;
  155.             if (pr == 0) {
  156.                 continue;
  157.             }
  158.             for (int j = N - 1; j >= 0; --j) {
  159.                 cur[2 * N - 1 - (N - 1 - i) - (N - 1 - j)] = (mid[j] * pr + dot) % 100;
  160.                 dot = (mid[j] * pr + dot) / 100;
  161.             }
  162.             dot = 0;
  163.             for (int j = 2 * N - 1; j >= 0; --j) {
  164.                 int x = (ans[j] + cur[j] + dot) / 100;
  165.                 ans[j] = (ans[j] + cur[j] + dot) % 100;
  166.                 dot = x;
  167.             }
  168.         }
  169.         bool great = false;
  170.         for (int i = 0; i < 2 * N; ++i) {
  171.             if (ans[i] > f[i]) {
  172.                 great = true;
  173.                 break;
  174.             }
  175.             else if (ans[i] < f[i]){
  176.                 break;
  177.             }
  178.         }
  179.         if (great) {
  180.             for (int i = 0; i < N; ++i) {
  181.                 right[i] = mid[i];
  182.             }
  183.         }
  184.         else {
  185.             for (int i = 0; i < N; ++i) {
  186.                 left[i] = mid[i];
  187.             }
  188.         }
  189.     }
  190.  
  191.     bool flag = true;
  192.  
  193.     for (int i = 0; i < N; ++i) {
  194.         if (left[i] == 0 && flag) {
  195.             continue;
  196.         }
  197.         else if (left[i] != 0 && flag) {
  198.             cout << left[i];
  199.             flag = false;
  200.         }
  201.         else {
  202.             if (left[i] < 10) {
  203.                 cout << 0;
  204.             }
  205.             cout << left[i];
  206.         }
  207.     }
  208.     return 0;
  209. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement