Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
- #pragma GCC optimize("unroll-loops")
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 200;
- bool lesen (int left[], int right[]) {
- int check[N];
- for (int i = 0; i < N; ++i) {
- check[i] = left[i];
- }
- for (int i = N - 1; i >= 0; --i) {
- if (check[i] < 99) {
- check[i] += 1;
- break;
- }
- else {
- check[i] = 0;
- }
- }
- for (int i = 0; i < N; ++i) {
- if (right[i] > check[i]) {
- return true;
- }
- else if (right[i] < check[i]) {
- return false;
- }
- else {
- }
- }
- return false;
- }
- void get_mid(int left[], int right[], int mid[]) {
- for (int i = 0; i < N; ++i) {
- mid[i] = 0;
- }
- int dot = 0;
- for (int i = N - 1; i >= 0; --i) {
- mid[i] = (right[i] + left[i] + dot) % 100;
- dot = (right[i] + left[i] + dot) / 100;
- }
- for (int i = 0; i < N; ++i) {
- if (i != N - 1)
- mid[i + 1] += 100 * (mid[i] % 2);
- mid[i] = mid[i] / 2;
- }
- }
- int main()
- {
- string a, b;
- cin >> a >> b;
- int left[N];
- int right[N];
- int mid[N];
- int cur[2 * N];
- int ans[2 * N];
- int f[2 * N];
- int s[2 * N];
- for (int i = 0; i < 2 * N; ++i) {
- f[i] = 0;
- }
- for (int i = 0; i < 2 * N; ++i) {
- s[i] = 0;
- }
- if ((int)a.size() % 2 == 1) {
- f[2 * N - (int)a.size() / 2 - 1] = (int) (a[0] - '0');
- for (int i = (int)a.size() - 1; i >= 2; i -= 2) {
- f[2 * N - (int)a.size() / 2 + i / 2 - 1] = ((int)(a[i - 1] - '0') * 10 + (int)(a[i] - '0'));
- }
- }
- else {
- for (int i = (int)a.size() - 1; i >= 1; i -= 2) {
- f[2 * N - (int)a.size() / 2 + i / 2] = ((int)(a[i - 1] - '0') * 10 + (int)(a[i] - '0'));
- }
- }
- if ((int)b.size() % 2 == 1) {
- s[2 * N - (int)b.size() / 2 - 1] = (int)(b[0] - '0');
- for (int i = (int)b.size() - 1; i >= 2; i -= 2) {
- s[2 * N - (int)b.size() / 2 + i / 2 - 1] = ((int)(b[i - 1] - '0') * 10 + (int)(b[i] - '0'));
- }
- }
- else {
- for (int i = (int)b.size() - 1; i >= 1; i -= 2) {
- s[2 * N - (int)b.size() / 2 + i / 2] = ((int)(b[i - 1] - '0') * 10 + (int)(b[i] - '0'));
- }
- }
- for (int i = 0; i < 2 * N; ++i) {
- if (s[i] < f[i]) {
- break;
- }
- else if (s[i] > f[i]) {
- cout << 0;
- return 0;
- }
- else {
- continue;
- }
- }
- int summ = 0;
- for (int i = 0; i < 2 * N; ++i) {
- summ += s[i];
- }
- if (summ == 1 && s[2 * N - 1] == 1) {
- cout << a;
- return 0;
- }
- int st = 0;
- while (f[st] == 0 && st < 2 * N) {
- st += 1;
- }
- if (st == 2 * N) {
- cout << 0;
- return 0;
- }
- for (int i = 0 ; i < N; ++i) {
- left[i] = 0;
- right[i] = f[N + i];
- }
- left[N - 1] = 1;
- while (lesen(left, right)) {
- for (int i = 0; i < N; ++i) {
- mid[i] = 0;
- }
- get_mid(left, right, mid);
- for (int i = 0; i < 2 * N; ++i) {
- ans[i] = 0;
- }
- for (int i = N - 1; i >= 0; --i) {
- for (int j = 0; j < 2 * N; ++j) {
- cur[j] = 0;
- }
- int pr = s[N + i]; int dot = 0;
- if (pr == 0) {
- continue;
- }
- for (int j = N - 1; j >= 0; --j) {
- cur[2 * N - 1 - (N - 1 - i) - (N - 1 - j)] = (mid[j] * pr + dot) % 100;
- dot = (mid[j] * pr + dot) / 100;
- }
- dot = 0;
- for (int j = 2 * N - 1; j >= 0; --j) {
- int x = (ans[j] + cur[j] + dot) / 100;
- ans[j] = (ans[j] + cur[j] + dot) % 100;
- dot = x;
- }
- }
- bool great = false;
- for (int i = 0; i < 2 * N; ++i) {
- if (ans[i] > f[i]) {
- great = true;
- break;
- }
- else if (ans[i] < f[i]){
- break;
- }
- }
- if (great) {
- for (int i = 0; i < N; ++i) {
- right[i] = mid[i];
- }
- }
- else {
- for (int i = 0; i < N; ++i) {
- left[i] = mid[i];
- }
- }
- }
- bool flag = true;
- for (int i = 0; i < N; ++i) {
- if (left[i] == 0 && flag) {
- continue;
- }
- else if (left[i] != 0 && flag) {
- cout << left[i];
- flag = false;
- }
- else {
- if (left[i] < 10) {
- cout << 0;
- }
- cout << left[i];
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement